83动态规划法求解背包问题

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

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

3、 输入相应的测试值，进行判断程序的正确性；关键代码int Knap(int n,int w,int v,int x,int C)int i,j;for(i=0;i<=n ;i+)ViO=O;for(j=0;j<=C;j+)V0j=0;for(i=0;i<=n _1;i+)for(j=0;j<=C;j+)if(j<wi)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-wi+vi);j=C;for( i=n-1;i>=0;i_)if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0;printf("选中的物品是：n

4、");for(i=0;i <n ;i+)prin tf("%d ”,xi);prin tf("n ”);return Vn-1C;测试结果e，一学w,算注活匸匕 m：；:-七hr-=-i- -9i貂人EWI品数=备分别轲入物品的重，11必 12 23 11 24请Q輸入物品的侨值：23 平 23 i3 强用中的和吊是，U 1 n 1 1H-_ 1实验心得通过这次实验，我回顾了 0-1背包问题的动态规划算法，因此更加深刻的了解 到动态规划算法的思想，由最优子结构来求解整个结构的最优结构，在进行实验的过程最重要的一步就是通过分析得到问题的动态规划方程，因此就根据

5、动态规划方程来实现代码。这个过程中最难的一步就是分析得到动态规划方程， 需要考虑各个可能的因素，最后再来用代码实现。 这次的实验难度相比于前两次实验，明显难多了，但是对于动态规划算法的认识也颇多，理解也更加深刻了。实验得分助教签名附录：完整代码#in clude<stdlib.h>#in clude<stdio.h>int V200200; 前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b) /一个大小比较函数，用于当总重大于第I行时if(a>=b)return a;else return b;int Knap(int n,int

6、 w,int v,int x,int C)int i,j;for(i=0;i<=n ;i+)ViO=O;for(j=0;j<=C;j+)V0j=0;for(i=0;i<=n-1;i+)for(j=0;j<=C;j+)if(j<wi)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-wi+vi);j=C;for(i=n-1;i>=0;i-)if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0;printf(" 选中的物品是 :n");for(i=0;i<n;i+)printf("%d &

7、quot;,xi);printf("n");return Vn-1C;int main()int s;/获得的最大价值int w4;/物品的重量int v4;/物品的价值int x4;/物品的选取状态选中则是 1int n,i;int C;/背包最大容量n=4;printf("请输入背包的最大容量:n");没选中为 0scanf("%d",&C);printf(" 物品数 :n");scanf("%d",&n);printf(" 请分别输入物品的重量 :n");for(i=0;i<n;i+)scanf("%d",&wi);printf(" 请分别输入物品的价值 :n");for(i=0;i<n;i+)scanf("%d",&vi);s=