//0-1背包問題(動態(tài)規(guī)劃法)

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

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

void Traceback(int b, int n, int x[])
{
	if(m[1][b]==m[2][b])x[1]=0;
	else{
		int j=1;
		while((m[1][b]-j*v[1])!=m[1][b-j*w[1]]&&m[1][b-j*w[1]]!=m[2][b-j*w[1]]+v[1])j++;
		x[1]=j;
	}
	for(int i=2; i<=n; i++){
		x[i]=(m[i][b]-m[i][b-x[i-1]*w[i]])/v[i];
		b-=w[i];
	}
}

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(B-1, N-1);
	Traceback(B-1, N-1, x);

	cout<<endl<<"m:"<<endl;
	for(i=1; i<N; i++)
	{
		for(int j=1; j<B; j++) cout<<m[i][j]<<"   ";
		cout<<endl;
	}
	cout<<"B = "<<B-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<<"Weight:"<<w1<<'\t'<<"Value:"<<m[1][B-1]<<endl;
}