动态规划法求解背包问题

《动态规划法求解背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第3次实验姓名杨玉茹学号201508010325班级计科1503时间3.31下午地点软件大楼330实验名称动态规划法求解背包问题实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。实验原理使用动态规划算法的原理，即将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。分析出背包问题的动态规划方程式，然后实现相应的代码，然后再进行再输入多组值进行验证，看输出结果，然后来验证自己的程序是否正确。实验步骤①首先求出最优子结构，设（y1,y2,..

2、.,yn）是所给0-1背包问题的一个最优解；②如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包，得出方程为：  V(i,0)=V(0,j)=0③如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，

3、取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解： V(i,j)=V(i-1,j) jwi④输入相应的测试值，进行判断程序的正确性；关键代码intKnap(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j++)if(

4、j=0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("选中的物品是:");for(i=0;i

5、规划算法，因此更加深刻的了解到动态规划算法的思想，由最优子结构来求解整个结构的最优结构，在进行实验的过程最重要的一步就是通过分析得到问题的动态规划方程，因此就根据动态规划方程来实现代码。这个过程中最难的一步就是分析得到动态规划方程，需要考虑各个可能的因素，最后再来用代码实现。这次的实验难度相比于前两次实验，明显难多了，但是对于动态规划算法的认识也颇多，理解也更加深刻了。实验得分助教签名附录：完整代码#include#includeintV[200][200];//前i个物品装入

6、容量为j的背包中获得的最大价值intmax(inta,intb)//一个大小比较函数，用于当总重大于第I行时{if(a>=b)returna;elsereturnb;}intKnap(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j++)if(j

7、=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;for(i=n-1;i>=0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("选中的物品是:");for(i=0;i

8、品的选取状态选中则是1没选中为0intn,i;intC;//背包最大容量n=4;printf("请输入背包的最大容量:");scanf("%d",&C);printf("物品数:");scanf("%d",&n);printf("请分别输入物品的重量:");for(i=0;i