实验2用动态规划实现01背包问题.docx

实验二用动态规划实现0-。。  :.给定n种物品和一个背包。物品i的重量是w,其价值为v,背包容量为c。问应该如何选择装入背包的物品,使得装入背包中物品的总价值最大?要求:使用动态规划算法编程,求解0-(1)#include<iostream>usingnamespacestd;intoptp[100][100];voidKnapsack(intm,intn,intw[10],intp[10])//n位物品数,m为背包的承受重量{ for(inti=0;i<=m;i++) { optp[0][i]=0; } for(intk=1;k<=n;k++) { optp[k][0]=0; for(intj=1;j<=m;j++) { if(w[k]<=j) { if(p[k]+optp[k-1][j-w[k]]>optp[k-1][j]) optp[k][j]=p[k]+optp[k-1][j-w[k]]; elseoptp[k][j]=optp[k-1][j]; } else optp[k][j]=optp[k-1][j]; } }}voidTraceback(intm,intn,intw[10],intx[10]){ intsum=0; for(intk=n;k>=1;k--) { if(optp[k][m]==optp[k-1][m]) x[k]=0; else { x[k]=1; m=m-w[k]; sum=sum+w[k]; } } x[1]=optp[1][m]?1:0; cout<<"最大总重量:"<<sum<<endl;}voidmain(){ intn,m; intw[10],p[10],x[10];c