实验4 “0-1”背包问题(2)

}

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");

}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库实验4 “0-1”背包问题(2)在线全文阅读。