背包问题动态规划详解及C代码.doc

《背包问题动态规划详解及C代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0/1背包问题动态规划详解及C++代码1.问题描述给定一个载重量为C的背包有n个物品其重量为wi价值为vi1<=i<=n要求:把物品装入背包并使包内物品价值最大2.问题分析在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。循环变量ij意义前i个物品能够装入载重量为j的背包中数组c意义c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值若w[i]>j第i个物品不装入背包否则若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j]则记录当前最大价值替换为第i个物品装入背包后的价值其c++代码如下#include<

2、iostream>usingnamespacestd;voidKANPSACK_DP(intc[50][50],intw[50],intv[50],intn,intC){for(inti=0;i<=C;i++){c[0][i]=0;}for(inti=1;i<=n;i++){c[i][0]=0;for(intj=1;j<=C;j++){if(w[i]<=j){if(v[i]+c[i-1][j-w[i]]>c[i-1][j])c[i][j]=v[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}elsec[i][j]=c[i-1][j];}}}voi

3、dOUTPUT_SACK(intc[50][50],intx[50],intw[50],intn,intC){for(intk=n;k>=2;k--){if(c[k][C]==c[k-1][C])x[k]=0;else{x[k]=1;C=C-w[k];}}x[1]=c[1][C]?1:0;}intmain(){intc[50][50];intw[50],v[50];intx[50];intC,n;cout<<"输入物品的总个数";cin>>n;cout<<"输入背包的总容量";cin>>C;cout<<"依次输入物品的重量"<

4、+){cin>>w[i];}cout<<"依次输入物品的价值"<>v[i];}KANPSACK_DP(c,w,v,n,C);OUTPUT_SACK(c,x,w,n,C);cout<<"最优解为"<

5、品的价值63546最优解为11001最大容量为15请按任意键继续...