#include "iostream.h"
int min(int a,int b)
{
if(a>=b) return b;
else return a;
}
int max(int a,int b)
{
if(a>=b) return a;
else return b;
}
void Knapsack(int v[6],int w[6],int c,int n,int m[6][6])
{
int jmax=min(w[n]-1,c);
for(int j=0;j<jmax;j++)
m[n][j]=0;
for(int p=w[n];p<=c;p++)
m[n][p]=v[n];
for(int i=n-1;i>1;i--)
{
jmax=min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int t=w[i];t<=c;t++)
m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]);
}
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}
void Traceback(int m[6][6],int w[6],int c,int n,int x[6])
{
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()
{
int n1=5;
int c1;
int w1[6]={0,2,2,6,5,4};
int v1[6]={0,6,3,5,4,6};
int t[6][6];
int x1[6];
cout<<"请输入背包的容量："<<endl;
cin>>c1;
cout<<"0-1背包问题是："<<endl;
cout<<"物品的重量分别为："<<endl;
for(int p=1;p<6;p++)
cout<<w1[p]<<" ";
cout<<endl;
cout<<"物品的价值分别为："<<endl;
for(int q=1;q<6;q++)
cout<<v1[q]<<" ";
cout<<endl;
cout<<"背包的容量为："<<c1<<endl;
cout<<"要选择的物品是:"<<endl;
Knapsack(v1,w1,c1,n1,t);
Traceback(t,w1,c1,n1,x1);
for(int i=1;i<=n1;i++)
if(x1[i]==1)
cout<<"第"<<i<<"件物品"<<"\t";
}
