//0-1背包問題(動態規劃法)

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define C 16
#define N 6
int w[N], v[N], m[N][C]={0};

void Knapsack(int c, int n)
{
	int jMax=w[n]-1<c ? w[n]-1 : c;
	for(int j=w[n]; j<=c; j++) m[n][j]=v[n];
	for(int i=n-1; i>1; i--)
	{
		jMax=w[i]-1<c ? w[i]-1 : c;
		for(j=0; j<=jMax; j++) m[i][j]=m[i+1][j];
		for(j=w[i]; j<=c; j++)
			m[i][j]=m[i+1][j]>m[i+1][j-w[i]]+v[i] ? m[i+1][j] : m[i+1][j-w[i]]+v[i];
	}
	m[1][c]=m[2][c];
	if(c>=w[1]) m[1][c]=m[1][c]>m[2][c-w[1]]+v[1] ? m[1][c] : m[2][c-w[1]]+v[1];
} // 算法的時間復雜度為O(nc)

void Traceback(int c, int n, int x[])
{
	for(int i=1; i<n; i++)
		if(m[i][c]==m[i+1][c]) x[i]=0;
		else
		{
			x[i]=1;
			c-=w[i];
		}
		x[n]=m[n][c]>0 ? 1 : 0;
}

void main()
{
	srand(time(0));
	cout<<"w:"<<endl;
	for(int i=1; i<N; i++)
	{
		w[i]=rand()%10+1;
		cout<<w[i]<<'\t';
	}
	cout<<endl<<"v:"<<endl;
	for(i=1; i<N; i++)
	{
		v[i]=rand()%20+10;
		cout<<v[i]<<'\t';
	}

	int x[N]={0};
	Knapsack(C-1, N-1);
	Traceback(C-1, N-1, x);

	cout<<endl<<"m:"<<endl;
	for(i=1; i<N; i++)
	{
		for(int j=1; j<C; j++) cout<<m[i][j]<<"   ";
		cout<<endl;
	}
	cout<<"C = "<<C-1<<endl;
	cout<<"x:"<<endl;
	int w1=0, v1=0;
	for(i=1; i<N; i++)
	{
		cout<<x[i]<<'\t';
		w1+=x[i]*w[i];
		v1+=x[i]*v[i];
	}
	cout<<endl<<w1<<'\t'<<v1<<endl;
}