[精品]动态规划解决0-1背包问题实验及其代码

《[精品]动态规划解决0-1背包问题实验及其代码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告3动态规划实验3动态规划解决0-1背包问题一、实验目的1)掌握动态规划动态方程的递归原理和过程；2)利用动态规划方法解决0・1背包问题；二、实验内容动态规划解决0・1背包问题三、算法设计1)编写voidValue(Typep[],Typew[],Typec,Typen,Typef[nMax][nMax])函数，用以计算各个最优子序列的值；2)编写voidcompute(Typef[nMax][nMax],Typew[],Typep[],Typec,Typen,Typex[])函数用以确定计算装入的物品x[]和装入的物品的总重量tot

2、alWeight；3)编写主函数，控制输入输岀；4)改进和检验程序。四、程序代码//动态规划算法解决-1背包问题的C++程序#ineludez，stdafx.h〃#include〈iostreani>#include〈iomanip〉usingnamcspacestd;inttotalWeight=0;//物品的总重量constintnMax二100;templatevoidValue(Typep[],Typew[],Typec,Typen,Typef[nlax][nlax]){//计算value]i][j]//置

3、初值条件for(intj二0;j〈二c;j++)if(j>=w[0])f[0][j]=p[0];elsef[O][j]=O;//计算各问题的最优值for(inti=1;i〈n;i++){for(intj=0;j<=c;j++)if(j>=w[i]&&f[i-1][j]voidcompute(Typef[nMax][nMax],Typew[],Typep[],Typec,Typen,Typex[]

4、){//计算x[]的值和装入的物品的总重量totalWeight；intc0=c,totalValue=0;for(inti二nT;i>0;i--)if(f[i][cO]>f[i-l][cO]){x[i]=l;c0=c0~w[i];totalValue二totalValue+p[i];totalWcight二toteilWcight+w[i];}elsex[i]=0;if(f[n~l][c]>totalValue){x[0]=l;totalWeight=totalWeight+w[0];Ielsex[0]=0;Iint_tmain(inta

5、rgc,_TCHAR*argv[]){inti,x[nMax],^weight,*price,volume,counts,value[nMax][nMax];charname[nMax][30];//物品的名称cout«〃请输入背包的容量，z«endl;cin>>volumc;//背包的容量cout«，/请输入待装物品的总个数，z«endl;cin>>counts;//物品的个数weight二newint[counts];//物品重量price二newint[counts];//物品的单价cout«〃请输入各个物品的名称：重量：价值:,z«

6、endl;for(i=0;i>name[i]>>weight[i]>>pricc[i];Value(price,weight,volume,counts,value);compute(value,weight,price,volume,counts,x);cout«，，0-lH包问题(装入背包的物品重量，价值，名字以表格的形式表示如下：)/z«endl;cout<

7、znamc[i]，?<

8、实现递归功能，大大减少了时间复杂度。运行结果如上所示，效果较佳!