}
for(i = n-1; i >= 1; i--) //控制物品的循环,从i-1到第1件
{
for(j = 0; j < w[i]; j++) //贪心法把此行注释
m[i][j]=m[i+1][j]; //贪心法把此行注释
for(j=w[i]; j<=c; j++)
m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
for(i = 1; i < n; i ++) //构造最优解
{
if(m[i][c] == m[i+1][c])
x[i] = 0;
else
{
x[i] = 1;
c = c-w[i];
}
}
x[n] = (m[n][c])?1:0; //m[n][c]大于0吗？大于就是选了
return;
}
void main()
{
int i=0,n=7;
int w[]={0,2,3,5,7,1,4,1};
int v[]={0,10,5,15,7,6,18,3};
int x[]={0,0,0,0,0,0,0,0};
cout<<"程序自带数据为："<<"\n";
cout<<"编号 重量 价值"<<endl;
for ( i=0;i<n;i++)
{
cout<<" "<<i+1<<" "<<w[i+1]<<" "<<v[i+1]<<endl;
}
int m=15;
int array[8][100]={0};
ZeroOneBag(v,w,x,m,7,array);
cout<<"\n背包能装的最大价值为: "<<array[1][m];
cout<<"\n\n最优解为:";
for(i = 1; i <= n; i++)
cout<<" "<<x[i]<<" ";
cout<<"\n\n";
system("pause");
}