动态规划解决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[]和装入的物品的

2、总重量totalWeight；3）编写主函数，控制输入输出；4）改进和检验程序。四、程序代码//动态规划算法解决-1背包问题的c++程序#include"stdafx.h"#include#includeusingnamespacestd;inttotalWeight=0;//物品的总重量constintnMax=100;templatevoidValue(Typep[],Typew[],Typec,Typen,Typef[nMax][nMax]){//计算value[

3、i][j]//置初值条件for(intj=0;j<=c;j++)if(j>=w[0])f[0][j]=p[0];elsef[0][j]=0;//计算各问题的最优值for(inti=1;i=w[i]&&f[i-1][j]voidcompute(Typef[nMax][nMax],Typ

4、ew[],Typep[],Typec,Typen,Typex[]){//计算x[]的值和装入的物品的总重量totalWeight；intc0=c,totalValue=0;for(inti=n-1;i>0;i--)if(f[i][c0]>f[i-1][c0]){x[i]=1;c0=c0-w[i];totalValue=totalValue+p[i];totalWeight=totalWeight+w[i];}elsex[i]=0;if(f[n-1][c]>totalValue){x[0]=1;totalWeight=totalW

5、eight+w[0];}elsex[0]=0;}int_tmain(intargc,_TCHAR*argv[]){inti,x[nMax],*weight,*price,volume,counts,value[nMax][nMax];charname[nMax][30];//物品的名称cout<<"请输入背包的容量"<>volume;//背包的容量cout<<"请输入待装物品的总个数"<>counts;//物品的个数weight=newint[counts];//物品重量price=new

6、int[counts];//物品的单价cout<<"请输入各个物品的名称:重量:价值:"<>name[i]>>weight[i]>>price[i];Value(price,weight,volume,counts,value);compute(value,weight,price,volume,counts,x);cout<<"0-1背包问题（装入背包的物品重量，价值，名字以表格的形式表示如下：）"<

7、2)<<"wieght[i]"<

8、t;//释放内存空间；delete[]price;return0;}五、运行结果六、结果分析此程序采用非递归方法实现递归功能，大大减少了时间复杂度。运行结果如上所示，效果较佳！