01背包问题动态规划详解及C++代码

0/1背包问题动态规划详解及C++代码1.问题描述给定一个载重量为C的背包有n个物品其重量为价值为要求:把物品装入背包并使包内物品价值最大2.问题分析在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。循环变量意义前i个物品能够装入载重量为j的背包中数组c意义表示前i个物品能装入载重量为j的背包中物品的最大价值若第i个物品不装入背包否则若w[i]=j且第i个物品装入背包后的价值c[i-则记录当前最大价值替换为第i个物品装入背包后的价值其c++代码如下#includeiostreamusingnamespacestd;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];}}}voidOUTPUT_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输入物品的总个数cinn;cout输入背包的总容量cinC;cout依次输入物品的重量for(inti=1;i=n;i++){cinw[i];}cout依次输入物品的价值for(inti=1;i=n;i++){cinv[i];}KANPSACK_DP(c,w,v,n,C);OUTPUT_SACK(c,x,w,n,C);cout最优解为for(inti=1;i=n;i++){coutx[i];}coutendl最大容量为coutc[n][C]endl;system(pause);return0;}运行结果如下输入物品的总个数输入背包的总容量依次输入物品的重量依次输入物品的价值最优解为最大容量为请按任意键继续...