背包问题的回溯法求解实验报告

背包问题的回溯法求解实验报作者:日期:、实验目的(1) 理解回溯法的思想2) 掌握一些经典的问题解决方法二、实验内容与实验步骤0-1背包问题★问题描述给定n种物品和一背包物品i的重量是wi>0,其价值为vi>0,背包的容量为 c问应如何选择装入背包中的物品，使得装入背包中物品的总价值最 大？★编程任务利用回溯法试设计一个算法求出0-1背包问题的解，也就是 求出一个解向量xi(xi = 0或l,xi = 0表示物体i不放入背包，xi =1表示 把物体i放入背包)，使得尽量多的价值装入背包★数据输入由文件input.txt提供输入数据n, c,及每个物品的重量w[] 和价值v[]★结果输出程序运行结束时，将最优解输出到文件output.txt中输入文件示例input.txt4输出文件示例output.txt1 1 0 152 1 3 212 10 20 15三、实验环境操作系统Windows 7调试软件VC++6.0上机地点综合楼211四、问题分析(1)分析要解决的问题，给出你的思路，可以借助图表等辅助表达01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为O (2 n )左右搜索的具体方法如下：对于每一个物品i,对于该物品只有选与不选2个决 策，总共有n个物品，可以顺序依次考虑每个物品，这 样就形成了一棵解空间树：基本思想就是遍历这棵树，以枚举所有情况，最后 进行判断，如果重量不超过背包容量，且价值最大的 话，该方案就是最后的答案。

利用回溯算法写还可以加入一些优化，进行剪枝， 因为很多情况是没有意义的，例如当重量大于背包容量 的时候，没有必要对剩下的物品再来决策了或者将剩 下的所有物品都选取其总价值也没有目前已经求得的方 案的价值还大的话，也是可以剪枝的2)分析利用你的想法解决该问题可能会有怎样的时空复杂度时间复杂度估计：O (2 n )因为物品只有选与不选2个决策，而总共有n个物 品，所以时间复杂度为O(2n)空间复杂度估计：O(n)因为递归栈最多达到n层，而且存储所有物品的信息也只需要常 数个一维数组，所以最终的空间复杂度为O(n)五、问题解决(1)根据对问题的分析，写出解决办法根据上面的分析，搜索的具体方法如下：对于每一个物品i,对于该物品只有选与不选2个决 策，总共有n个物品，可以顺序依次考虑每个物品，这样 就形成了一棵解空间树，由父亲节点往下搜索的时候， 往左表示选择该物品，并且将该物品的重量和价值追加 到总重量和总价值中，最后，当到达第n+1层的时候，表 示所有的物品都已经决策完了，可以比较和更新最优 值当所有的分支和节点都遍历完时，此时的最优值就 是原问题的最优值优化方法：剪枝一：可以进行剪枝，因为很多情况是没有意义 的，当重量大于背包容量的时候，没有必要对剩下的物 品再来决策了。

剪枝二：将剩下的所有物品都选取其总价值也没有 目前已经求得的方案的价值还大的话，也可以返回1) 描述你在进行实现时，主要的函数或操作内部的主要算法;分析这个算法的时、 空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述void Knapsack(Typep p[ ], Typew w[ ], Typew c, int n){ 〃为 Knap::Backtrack 初始化Typew W = 0;Typep P = 0;FILE *fp;Object * Q = new Object[n];for ( int i = 1; i <= n; i++ ) {Q[ i-1]. ID = i;Q[ i-1]. d =1.0*p[i]/w[i];P += p[i]； W += w[i];}Sort( Q, n);〃对背包里的物品按性价比排序Knap < Typew, Typep > K;K.p = new Typep[ n+1 ];K.w = new Typew[ n+1 ];K.x = new int[ n+1 ];for (i = 1; i <= n; i++){K.p[i] = p[ Q[i-1].ID];K.w[i] = w[ Q[i-1].ID];}K.cp = 0;K. cw = 0;K.c = c;K.n = n;K.bestp = 0;//回溯搜索K.Backtrack(1);delete [ ] Q;delete [ ] K.w;delete [ ] K.p;if ((fp=fopen("output.txt","w"))==NULL){fprintf(stderr, "Cannot open input file.\n"); exit(0);}fprintf(fp,"%d,%d,%d,%d",K.x[4],K.x[1],K.x[2],K.x[3]); fclose(fp);coutvv"当前最优装配:"；coutvvK.x[4];for (i=1;ivn;i++){coutvv" "<< K.x[i];}coutvvendl;}templatevclass Typew, class Typep>void KnapvTypew, Typep>:: Backtrack( int i) {if ( i > n ) {bestp = cp;return;}if( cw + w[i] <= c){x[i] = 1; cw += w[i]; cp += p[i];Backtrack(i+1); cw -= w[i];cp -= p[i];}if( Bound(i+1)> bestp)x[i] = 0;Backtrack(i+1);} templatevclass Typew, class Typep>Typep KnapvTypew, Typep>:: Bound( int i){ 〃计算上界Typew cleft = c-cw; 〃剩余容量Typep b = cp;〃以物品单位重量价值递减序装入物品while ( i<= n && w[i]<= cleft) {cleft -= w[i];b += p[i]; i++;}〃装满背包if( i<=n ) b+= p[i]/w[i]*cleft; return b;}算法复杂度：由于计算上界函数Bound需要O(n)时间，在最坏情况下有O(2n)个右儿子结点需 要计算上界函数，故解0-1背包问题的回溯算法Backtrack所需的计算时间为O(n2n)。

算法创新：增加了对于上限的处理函数，计算右子树中解的上界时，将剩余物品依其单位重量 价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包， 由此得到的价值是右子树的上界，如果这个上界不能达到当前得到的最优值，则不搜 索该子树2) 你在调试过程中发现了怎样的问题？又做了怎样的改进？答：在调试过程中，对于背包中物品顺序的保存始终存在问题，应该是1011，可是总是无法 得出正确的结果，所以，我对数组x[i]进行了单步调试，继而发现了在前面回溯法的设 计过程中存在缺陷，将x[4]误当成了 x[0]，后来经过改正输出正确六、实验结果总结本实验也是自己独立完成，从设计回溯法开始，到实现01背包问题的求解, 从中我学到了很多，从错误的改正过程中逐渐完成了对于问题的求解1•程序运行截图：se rs\TC\D-eskto算法窪自;宴验S\Debug\0lknapsack e.:

空间复杂度为O(n)，还可以接受但是综合上面分析，时间复杂度成为极大地瓶颈所以规模很大时不可以接 受2) 如果不用回溯方法还能想到其他的解决方式吗？和回溯法相比会有更好的效率吗?还可以用基于动态规划思想的算法在考虑第i个物品的决策时，前 面的物品的选择方案就成为了子问题，可以建立如下状态转移方程：f [i ][ j ] = maxf [i -1][ j ]f [i -1][ j - w[i ]] + v[i]其中f[i]j]表示前i个物品装入容量不超过j的背包的最优值时间复杂度为O(n*C)，其中C为背包容量时间复杂度比回溯法要好很多3) 所选用的数据结构合适吗？答：合适，只用到一维数组使用的数据结构简单，易理解能够对数组 中的每个元素随机访问4) 该算法都存在哪几类可能出现的情况，你的测试完全覆盖了你所想到的这些8 / 9情况吗，测试结果如何？ 答：测试全面输入规模为0时，程序自动结束输入总重量小于背包容量时，结果为所有物品的价值总和 输入的总重量大于背包容量时，结果为能装入所有方案中最 大的值5） 叙述通过实验你对回溯法方法的理解及其优缺点优点：回溯法在普通的深度优先搜索的基础上增加了限界 函数，对不必要的解空间树进行剪枝，使得可行解的数量大大减 少，增加了搜索速度。

回溯法的设计也非常简单，即简单的枚举搜索策略，只需要 分析细节过程就能增加剪枝的操作另外，空间复杂度通常非常小，只有搜索深度左右的空间 缺点：回溯法虽然设计简单，但是时间复杂度非常高，通 常是指数级别的而且回溯法的难点在于限界函数的设计而且回溯法通常需要遍历完所有的解空间才能得出最优值， 而不是像宽度优先搜索一样第一次求出的值便是最优值七、附录参考资料：《算法导论》。