动态规划法求解背包问题

1、算法分析与设计实验报告第三次实验姓名学号班级时间11.14上午地点工训楼309实验名称动态规划法求解背包问题实验目的通过上机实验，要求掌握动态规划算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用动态规划法的思想，把0-1背包装满并使得其价值最大。程序思路：（1）首先从剩余容量是考虑当前物品能不能放入背包；（2）其次从价值上考虑当前物品要不要放入背包，是不是最优的。实验步骤 找出最优解的性质，并刻画其结构特征（利用反证法）。 递归的定义最优值。 以自底向上的方法计算最优值。 根据计算最优值时的信息构造最优解。void Knapsack( int v, int w, int

2、c, int n, int m)/初始化0-1背包表格int jmax=min(wn,c);/背包剩余容量上限，范围0wn)(左闭右开区间)for (int j=0;jvjmax;j+)m nj=0;for (int j=wn;j<=c;j+)/ 限制范围wncm nj=v n;/利用最优子结构性质，从最后一个元素开始，利用递推公式for (int i=n-1;i>=1;i-)jmax=min(wn,c);/第一种情况，背包剩余容量j在区间0,jmax)，该物品不能放入背包for (int j=0;j<jmax;j+)mij=mi+1j;/没产生任何效益for (int j=

3、wi;j<=c;j+)/ 第二种情况，背包剩余容量j在区间wi,cmij=max(mi+1j,mi+1j-wi+vi);/关键代码不同之处在于o0表格的第一行的填法根据效益值增加vi，选择该物品放入背包或者不放入背包/x数组存储对应物品0-1向量，不装入背包，装入背包void Traceback( int *m, int w, int c, int n, int x)for (int i=1;i<n;i+)if (mic=mi+1c)/若前一个和后一个效益值比没变化，说明该物品没放入背包中xi=0;else /否则放入了背包中，由m2c-w1继续构造最优 解xi=1; c-=wi;

4、xn=(mnc)?1:0;/最后一个元素需要单独判断for(int i=n-1;i>1;i-)jmax=mi n(wn-1,c);for(int j=O;jv=jmax;j+)/ 背包不同剩余容量jv=jmax<cmij=mi+1j;/没产生任何效益for(int j=wi;j<=c;j+)/ 背包不同剩余容量j-wi>cmij=max(mi+1j,mi+1j-wi+vi);/ 效益值增加vi/之所以讲m1c单独拿出来计算，是为了计算的方便，并不需 要在和前面一样的麻烦，只有判断最后一步就可以m1c=m2c;if(c>=w1)m1c=max(m1c,m2c-w1+

5、v1);测试结果输入及背包容量较小的结果（数据手动收入）-F;算潼主堂0峻二就危规劲法Eb7 建項自（匚 tri-I-Shift + Mi |恃装掬品的价值两L 2 4 3o-n e 1D e-buqxe:ro- 口【门 u 1» exu输入及背包容量中等大小的结果（数据由随机函数产生）SJ®"J47ero-onelDebugTero-on el. exe101 1 jp 0 & & y/ I 10M 办54值均 ;1 '价号 =羲为59为59的编 容个值雪聶大盘 Es-i*!rF_JJOJ & -A- 6 0 t 匚 口-m 3

6、fiM 3 JDJ5 1 非覇品览品46萊下y 人入物6物&曙$ 71装71包包 718244time is H.HbZ输入及背包容量较大的结果（数据由随机函数产生）口-orclS Debugero-c iftel.cxei 阳*JL0O2V8Hb al 214HH V13L> 29HLH IV344 122H 14Kb& 2hAY 4M42 17VBb1005 6-®l 301U 444« 1464?291SP 2nR；» 曲乂27A27或忙,：世 t址 fLdJW虽L_：*i<Lc或？BET：Pij£盂 ivfekUFFm

7、TFTnI 解重.常工 Iff I' 卡 F 亍 I""f 卡 1： I? I.电才匚#JE *聊工 Ji 二耳i 1 屮左 ? y. yi.、jip【（.vrjfr*s 黑 / 】託! :i 念 w*eij:.!:鼻 myi i 硏.吊The 1 lw lx 6 _fWl实验心得对于这一次的实验，利用动态规划的算法求解 0-1背包问题，虽然课本上 有函数的实现但是实验做起来还是有一定的难度的，毕竟我们追求的不是将代码敲出来而是真正掌握了这一个经典的算法实例。首先我是自己写了主函数， 然后照着课本敲的代码，然后自己一步步分析代码中的不足的部分，加以完善，后来经过自己

8、对于这个问题的理解，发现课本上的代码有一些不太容易理解的地方，就按照自己的理解进行了一些改变，最终实现了将自己的理解与代码完全融合，后来自己又仔细研究了一下书上的代码，发觉自己的代码效率不高， 就有进行了改进，最终得到了较为满意的代码。不过在实验过程中也遇到了很多的问题，最主要的问题是经常出现中断，这使我很郁闷，不过好在在冋学的帮助下都顺利解决了， 感觉很开心，然后由于要测试大数据，所以采用了随机生成函数，以及动态分配内存，学的利用到很多以前不太用到的知识，感觉棒棒的。实验比较观察上面三种不同数据规模的输入，我们可以看到当物品的数量比较多的时候，算法是比较浪费时间的， 其次是背包的容量也是一种

9、限制性因素，而且采用随机生成函数有一点不好的就是生成的数据都是比较大的，有点不符合实际，我想在实际问题处理中应该采用的是读文件的方式输入的吧，不然采用手动输入，还是十分麻烦的。实验得分助教签名附录：完整代码0-1背包问题，动态规划算法#include <iostream>#inelude <time.h>#include <iomanip> using namespacestd;const int N=100;void Knapsack( int v, int w, int c, int n, int *m); void Traceback( int *m,

10、 int w, int c, int n, int x);/随机生成数组元素函数void ran( int *input,int n)int i;sran d(time(0);for (i=1;i<=n;i+)in puti=ra nd();/in puti='0'int main()int c,n;cout<< "请输入背包的容量： " cin>>c;cout<< "请输入物品的个数： " cin>>n;/ 下标从 1开始int *v= new int n+1;int *w= new

11、 int n+1;int xN+1;int *m;int i;m=new int *n+1;for (i=0;i<n+1;i+) mi= new int c;* 手动输入的代码部分 */*cout<<" 待装物品的重量为： "<<endl; for(i=1;i<=n;i+)cin>>wi; cout<<endl;cout<<" 待装物品的价值为： for(i=1;i<=n;i+) cin>>vi;cout<<endl;*/* 随机生成数据部分 * ran(v,n)

12、;cout<< "待装物品的价值为： for (i=1;i<=n;i+) cout<<vi<< " " ;cout<<endl;ran(w,n);cout<< "待装物品的重量为： for (i=1;i<=n;i+) cout<<wi<< " " ;cout<<endl;clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(

13、);"<<endl;" <<endl;" <<endl;/ 计算程序运行时间的算法Knapsack(v,w,c,n,m);/函数调用，求解 0-1 背包问题cout<< "背包能装的最大的价值为： " <<m1c<<endl;Traceback(m,w,c,n,x);/函数调用，构造最优解cout<< "背包装下的物品编号为： " <<endl; for (i=1;i<=n;i+)if (xi=1)cout<<i

14、<< " " ;cout<<endl; cout<<endl; end=clock();printf( "The time is %6.3f" ,( double )(end-start-over)/CLK_TCK); / 显 示运行时间for (i=0;i<n+1;i+) / 删除动态分配的内存delete mi;delete m;delete v;delete w;system( "pause" ); return 0;* 课本上的源代码部分 */*void Knapsack(int v,

15、int w,int c,int n,int m10) int jmax=min(wn-1,c); /背包剩余容量上限，范围 0wn-1for(int j=0;j<=jmax;j+) mnj=0;for(int j=wn;j<=c;j+) / mnj=vn;限制范围 wncfor(int i=n-1;i>1;i-) jmax=min(wn-1,c);for(int j=0;j<=jmax;j+)/mij=mi+1j;/背包不同剩余容量 j<=jmax<c 没产生任何效益for(int j=wi;j<=c;j+) / 背包不同剩余容量 j-wi>c

16、mij=max(mi+1j,mi+1j-wi+vi); / 效益值增加 vi m1c=m2c;if(c>=w1)m1c=max(m1c,m2c-w1+v1);*/void Knapsack( int v, int / 初始化 0-1背包表格 int jmax=min(wn,c);开区间)for (int j=0;j<jmax;j+) mnj=0;for (int j=wn;j<=c;j+) mnj=vn;w, int c, int n, int *m)/ 背包剩余容量上限，范围 0wn)( 左闭右/ 限制范围 wncfor (int i=n-1;i>=1;i-) jmax=min(wn,c);0,jmax) ，该物品不能放入背包 for (int j=0;j<jmax;j+) mij=mi+1j;for (int j=wi;j<=c;j+)/ 利用最优子结构性质，从最后一个元素开始，利用递推公式/ 第一种情况，背包剩余容量 j 在