动态规划法求解背包问题

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

2、，则装人前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的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解：  V(i,j)=V(i-1,j)  

3、j<wi    V(i,j)=maxV(i-1,j) ,V(i-1,j-wi)+vi) j>wi 输入相应的测试值，进行判断程序的正确性；关键代码int Knap(int n,int w,int v,int x,int C)int i,j;for(i=0;i<=n;i+)Vi0=0;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;

4、i-)if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0; printf("选中的物品是:n");for(i=0;i<n;i+)printf("%d ",xi);printf("n");return Vn-1C;测试结果 实验心得通过这次实验，我回顾了0-1背包问题的动态规划算法，因此更加深刻的了解到动态规划算法的思想，由最优子结构来求解整个结构的最优结构，在进行实验的过程最重要的一步就是通过分析得到问题的动态规划方程，因此就根据动态规划方程来实现代码。这个过程中最难的一步就是分析得到动态规划方程，需要考虑

5、各个可能的因素，最后再来用代码实现。这次的实验难度相比于前两次实验，明显难多了，但是对于动态规划算法的认识也颇多，理解也更加深刻了。实验得分助教签名附录：完整代码#include<stdlib.h>#include<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 w,int v,int x,int C)int i,j;for(i=0;i&l

6、t;=n;i+)Vi0=0;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 ",xi);printf("n");return Vn-

7、1C;int main()int s;/获得的最大价值int w4;/物品的重量 int v4;/物品的价值int x4;/物品的选取状态 选中则是1 没选中为0 int n,i;int C;/背包最大容量n=4;printf("请输入背包的最大容量:n");scanf("%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=Kn