回溯法求0-1背包问题.doc

《回溯法求0-1背包问题.doc》由会员分享，可在线阅读，更多相关《回溯法求0-1背包问题.doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流回溯法求0-1背包问题.精品文档.算法设计与分析实验报告学 号： 姓 名： 日 期： 得 分： 一、实验内容：用回溯法求解0/1背包问题注：给定种物品和一个容量为的背包，物品的重量是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。二、所用算法的基本思想及复杂度分析：1.回溯法求解背包问题：1） 基本思想：回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以

2、减少问题的计算量。这种具有限界函数的深度优先生成法称为回溯法。对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。当右子树中有可能包含最优解时就进入右子树搜索。2）复杂度分析：回溯法求解0/1背包问题的时间复杂度为：。空间复杂度：有个物品，即最多递归层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为。2.以动态规划法验证：1）基本思想：令表示在前个物品中能够装入容量为的背包中的物品的最大值，则可以得到如下动态函数：按照下述方法来划分阶段：第一阶段，只装入前1个物品，确

3、定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第个阶段。最后，便是在容量为的背包中装入个物品时取得的最大价值。2）复杂度分析：动态规划法求解0/1背包问题的时间复杂度为：。三、源程序及注释：#include#includeusing namespace std;struct goods/物品结构体int sign;/物品序号int w;/物品重量int v;/物品价值a100;bool m(goods a,goods b)return (a.v/a.w)(b.v/b.w);int max(int a,int b)re

4、turn an-1)if(bestPcp)for (int k=0;kn;k+)xk=cxk;/存储最优路径bestP=cp;return bestP;if(cw+ai.w=C)/进入左子树cw=cw+ai.w;cp=cp+ai.v;cxai.sign=1;/装入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.v;/回溯，进入右子树cxai.sign=0;/不装入背包BackTrack(i+1);return bestP;/回溯法求解0/1背包问题int KnapSack(int n,goods a,int C,int x)for(int i=0;in;i+)xi=0

5、;ai.sign=i;sort(a,a+n,m);/将各物品按单位重量价值降序排列BackTrack(0);return bestP;/动态规划法求解0/1背包问题int KnapSack1(int n,goods a,int C,int x)int V1001000;for(int i=0;i=n;i+)/初始化第0列Vi0=0;for(int j=0;j=C;j+)/初始化第0行V0j=0;for(i=1;i=n;i+)/计算第i行，进行第i次迭代for(j=1;j=C;j+)if(j0;i-)if (VijVi-1j)xi-1=1;j=j-ai-1.w;elsexi-1=0;return

6、 VnC;/返回背包取得的最大价值/测试以上算法的主函数int main()printf(物品种数n: );scanf(%d,&n);/输入物品种数printf(背包容量C: );scanf(%d,&C);/输入背包容量for (int i=0;in;i+)/输入物品i的重量w及其价值vprintf(物品%d的重量w%d及其价值v%d: ,i+1,i+1,i+1);scanf(%d%d,&ai.w,&ai.v);int sum1=KnapSack1(n,a,C,x);/调用动态规划法求0/1背包问题printf(动态规划法求解0/1背包问题:nX= );for(i=0;in;i+)coutxi

7、 ;/输出所求Xn矩阵printf(装入总价值%dn,sum1);int sum2=KnapSack(n,a,C,x);printf(回溯法求解0/1背包问题:nX= );for(i=0;in;i+)coutxi ;/输出所求Xn矩阵printf(装入总价值%dn,sum2);return 0;四、运行输出结果：相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果正是所求问题的最优解，以动态规划法验证回溯法求解的0/1背包问题是正确的。五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1.本实验中用回溯法求0/1背包问题，课本上给出的算法伪代码只能求出背包装入物品的最大总价值，所以我在对物品构造结构体时定义了一个int型变量sign，用来记录所给物品的原始顺序，并在适当位置记录装入和不装入背包，存储求解路径，从而求出原始问题的解向量X。2.在本实验中，本为增强回溯法求解0/1背包问题函数的可移植性，只定义局部变量而不定义全局变量，花费大量时间不断改进调试都未能达到目的，走了各种弯路，最终总是因为函数之间参数无法传递导致运行错误。这让我真正意识到了自己在参数传递、指针变量方面知识的掌握不太牢固，同时认识到了定义全局变量的一些好处，以后尽量不要片面追求所编函数的可移植性而拒用全局变量，以此为戒。