动态规划法求解背包问题.doc

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

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

2、ack(intv[],intw[],intc,intn,int**m){//初始化0-1背包表格intjmax=min(w[n],c);//背包剩余容量上限，范围[0~w[n])(左闭右开区间)for(intj=0;j=1;i--){jmax=min(w[n],c);//第一种情况，背包剩余容量j在区间[0,jmax)，该物品不能放

3、入背包for(intj=0;j

4、n;i++){if(m[i][c]==m[i+1][c])//若前一个和后一个效益值比没变化，说明该物品没放入背包中x[i]=0;else//否则放入了背包中，由m[2][c-w1]继续构造最优解{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;//最后一个元素需要单独判断}for(inti=n-1;i>1;i--){jmax=min(w[n]-1,c);for(intj=0;j<=jmax;j++)//背包不同剩余容量j<=jmax

5、++)//背包不同剩余容量j-w[i]>cm[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);/效益值增加vi}//之所以讲m[1][c]单独拿出来计算，是为了计算的方便，并不需要在和前面一样的麻烦，只有判断最后一步就可以m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);测试结果输入及背包容量较小的结果（数据手动收入）：输入及背包容量中等大小的结果（数据由随机函数产生）：输入及背包容量较大的结果（数据由随机函数产生）：实验心得对于这一次的实

6、验，利用动态规划的算法求解0-1背包问题，虽然课本上有函数的实现但是实验做起来还是有一定的难度的，毕竟我们追求的不是将代码敲出来而是真正掌握了这一个经典的算法实例。首先我是自己写了主函数，然后照着课本敲的代码，然后自己一步步分析代码中的不足的部分，加以完善，后来经过自己对于这个问题的理解，发现课本上的代码有一些不太容易理解的地方，就按照自己的理解进行了一些改变，最终实现了将自己的理解与代码完全融合，后来自己又仔细研究了一下书上的代码，发觉自己的代码效率不高，就有进行了改进，最终得到了较为满意的代码。不过在实验过程中也遇到了很多的问题，最主要的问题是经常出

7、现中断，这使我很郁闷，不过好在在同学的帮助下都顺利解决了，感觉很开心，然后由于要测试大数据，所以采用了随机生成函数，以及动态分配内存，学的利用到很多以前不太用到的知识，感觉棒棒的。实验比较观察上面三种不同数据规模的输入，我们可以看到当物品的数量比较多的时候，算法是比较浪费时间的，其次是背包的容量也是一种限制性因素，而且采用随机生成函数有一点不好的就是生成的数据都是比较大的，有点不符合实际，我想在实际问题处理中应该采用的是读文件的方式输入的吧，不然采用手动输入，还是十分麻烦的。实验得分助教签名附录：完整代码//0-1背包问题，动态规划算法#include<

8、iostream>#include#include