数据结构常见问题：12单元23 背包问题.docx

《数据结构常见问题：12单元23 背包问题.docx》由会员分享，可在线阅读，更多相关《数据结构常见问题：12单元23 背包问题.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程常见问题单元23背包问题i.背包问题如何用求解？解析：一、 问题描述0/1背包问题：现有n种物品，对ICiCn,第i种物品的重量为正整数Wi,价值为正整数Vi,背包能承受的最大 载重量为正整数肌 现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量 大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一局部）二、算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数:于是，问题就归结为寻找一个满足约束条件（1）,并使目标函数式（2）到达最大的解向量。首先说明一下0T背包问题拥有最优解。假设是所给的问题的一个最优解，那么是下面问题的一个最优解：。如

2、果不是的话，设是这个问题的 一个最优解，那么，且。因此，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。穷举法：用穷举法解决0T背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不 超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。由于程序过于简单, 在这里就不再给出，用实例说明求解过程。下面给出了 4个物品和一个容量为10的背包，下列图就是用穷 举法求解0-1背包问题的过程。（a）四个物品和一个容量为10的背包序号 子集 总重量 总价值 序号 子集 总重量 总价值1空集2 1 73 2 34 3 45 4 56 1, 21空集2 1 7

3、3 2 34 3 45 4 56 1, 20042 1012 1140 1225 1310 5492,37522,48373,49651,2,3) 14不可行14 1,3,4 16 不可行1,2,4) 15不可行7 1, 3 11不可行8 1, 4 12不可行7 1, 3 11不可行8 1, 4 12不可行15 (2, 3, 4) 12 不可行16 (1,2,3,419 不可行（b）用回溯法求解0-1背包问题的过程递归法：在利用递归法解决0-1背包问题时，我们可以先从第n个物品看起。每次的递归调用都会判断两种情况:（1）背包可以放下第n个物品，那么xn = l,并继续递归调用物品重量为W-wn

4、,物品数目为n-1的递 归函数，并返回此递归函数值与vn的和作为背包问题的最优解；（2）背包放不下第n个物品，那么xn=0,并继续递归调用背包容量为肌物品数目为nT的递归函数, 并返回此递归函数值最为背包问题的最优解。递归调用的终结条件是背包的容量为0或物品的数量为0.此时就得到了 0-1背包问题的最优解。用递归法解0-1背包问题可以归结为下函数：第一个式子表示选择物品n后得到价值比不选择物品n情况下得到的价值小，所以最终还是不选择 物品n;第二个式子刚好相反，选择物品n后的价值不小于不选择物品n情况下得到了价值，所以最终选 择物品no在递归调用的过程中可以顺便求出所选择的物品。下面是标记物品

5、被选情况的数组xn求解的具体函 数表示：在函数中，递归调用的主体函数为KnapSack, m表示背包的容量，n表示物品的数量，xn表示是 否选择了第n个物品（1一选，0一不选）。每个物品的重量和价值信息分别存放在数组wn和vn中。具 体的代码见递归法文件夹。贪心法：0T背包问题与背包问题类似，所不同的是在选择物品装入背包时，可以选择一局部，而不一定要全部 装入背包。这两类问题都具有最优子结构性质，相当相似。但是背包问题可以用贪心法求解，而0T背包 问题却不能用贪心法求解。贪心法之所以得不到最优解，是由于物品不允许分割，因此，无法保证最终能 将背包装满，局部闲置的背包容量使背包单位重量的价值降低

6、了。事实上，在考虑0T背包问题时，应比 较选择物品和不选择物品所导致的方案，然后做出最优解。由此导出了许多相互重叠的子问题，所以，0-1 背包问题可以用动态规划法得到最优解。在这里就不再用贪心法解0-1背包问题了。动态规划法分析：0-1背包问题可以看作是寻找一个序列，对任一个变量 的判断是决定=1还是=0.在判断完之后， 已经确定了，在判断时，会有两种情况：（1）背包容量缺乏以装入物品i,那么二0,背包的价值不增加；（2）背包的容量可以装下物品i,那么=1,背包的价值增加。这两种情况下背包的总价值的最大者应该是对判断后的价值。令表示在前i个物品中能够装入容量为 j的背包的物品的总价值，那么可以

7、得到如下的动态规划函数：式（1）说明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价 值均为0.式（2）第一个式子说明：如果第i个物品的重量大于背包的容量，那么装入第i个物品得到的最 大价值和装入第iT个物品得到的最大价值是相同的，即物品i不能装入背包中；第二个式子说明：如果 第i个物品的重量小于背包的容量，那么会有两种情况：（1）如果把第i个物品装入背包，那么背包中物品的 价值就等于把前iT个物品装入容量为的背包中的价值加上第i个物品的价值；（2）如果第i个物品没 有装入背包，那么背包中物品的价值就是等于把前iT个物品装入容量为j的背包中所取得的价值。显然， 取二者

8、中价值较大者作为把前i个物品装入容量为j的背包中的最优解。我们可以一步一步的解出我们所需要的解。第一步，只装入第一个物品，确定在各种情况下背包 能得到的最大价值；第二步，只装入前两个物品，确定在各种情况下的背包能够得到的最大价值；一次类 推，到了第n步就得到我们所需要的最优解了。最后，便是在容量为W的背包中装入n个物品时取得的 最大价值。为了确定装入背包的具体物品，从的值向前寻找，如果，说明第n个物品被装入了背包中， 前n-l个物品被装入容量为的背包中；否那么，第n个物品没有装入背包中，前n-l个物品被装入容量为W 的背包中。依此类推，直到确定第一个物品是否被装入背包为止。由此，我们可以得到如

9、下的函数：.根据动态规划函数，用一个的二维数组C存放中间变量，表示把前i个物品装入容量为j的背 包中获得的最大价值。设物品的重量存放在数组wn中，价值存放在数组vn中，背包的容量为肌数组存放迭代的结 果，数组xn存放装入背包的物品，动态规划解0T背包问题的源代码在文件夹动态规划法中。 回溯法分析：用回溯法解0背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行 结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否那么将右子树剪去。设r 是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rWbestp时丁可剪去右子树。 计算右子

10、树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不 下时，再装入该物品的一局部而装满背包。由此得到的价值是右子树中解的上界，用此值来剪枝。为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可。在实 现时，由MaxBoundary函数计算当前结点处的上界。它是类Knap的私有成员。Knap的其他成员记录了解 空间树种的节点信息，以减少函数参数的传递以及递归调用时所需要的栈空间。在解空间树的当前扩展结 点处，仅当要进入右子树时才计算上界函数MaxBoundary,以判断是否可以将右子树减去。进入左子树时 不需要计算上界，因为其上界与

11、父结点的上界相同。在调用函数Knapsack之前，需要先将各物品依其单位重量价值从到达小排序。为此目的，我们定义了 类Objiect。其中，运算符与通常的定义相反，其目的是为了方便调用已有的排序算法。在通常情况下， 排序算法将待排序元素从小到大排序。在搜索状态空间树时，由函数Backtrack控制。在函数中是利用递归调用的方法实现了空间树的搜索。 具体的代码见回溯法文件夹。限界分支法：在解0-1背包问题的优先队列式界限分支法中，活结点优先队列中结点元素N的优先级由该结点的上界 函数MaxBounda叮计算出的值uprofit给出。该上界函数在0T背包问题的回溯法总已经说明过了。子集 树中以结点

12、N为根的子树中任一个结点的价值不超过N. prof it。因此我们用一个最大堆来实现活结点优先 队列。堆中元素类型为IleapNode,其私有成员有uprofit, profit, weight, level,和ptro对于任意一个活 结点N, N. weight是活结点N所相应的重量;N.profit是N所相应的价值;N.uprofit是结点N的价值上 界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。在分支限界法中用到的类Knap与0-1背包问题的回溯法中用到的类Knap很相似。他们的区别是新的类 中没有了成员变量bestp,而增加了新的成员bestx。Bestxi=l,当

13、且仅当最优解含有物品i。在类Knap中有四个函数：(1)上界函数MaxBoundaO,计算节点所对应价值的上界；(2)函数AddLiveNodeO是将一个新的活结点插入到子集树和优先队列中；(3)函数MaxKnapsackO实施对子集树的优先队列式分支界限搜索。其中假定物品依其单位价值从大 到小已经排好序。相应的排序过程会在算法的预处理局部完成。算法中E是当前扩展结点；cw是该结点的 重量；cp是该结点的价值；up是价值上界。算法的while循环不断扩展结点，直到子集树的一个叶结点 成为扩展结点为止。此时优先队列中所有活结点的价值上界均不超过该叶结点的价值。因此该叶结点相应 的解为问题的最优解

14、。在while循环内部，算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点, 那么将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点 满足上界约束时才将它加入子集树和活结点优先队列。(4)函数Knapsack ()完成对输入数据的处理。其主要任务是将各物品依其单位重量价值从到达小排好 序。然后调用函数MaxKnapsackO完成对子集树的优先队列式分支限界搜索。具体的实现代码在文件夹分支限界法中。三、时空效率分析穷举法：对于一个有n个元素的集合，其子集数量为，所以，不管生成子集的算法效率有多高，穷举法都会 导致一个的算法。递归法：在

15、递归法的算法体中有一个if判断中出现了两次递归调用比拟大小所以它们之间的递归关系式可 以大体表示为：，其中表示递归法的时间复杂度，C是常数。求解递归方程可以知道的量级为。所以 递归法解0-1背包问题的时间复杂度为。递归法是耗费空间最多的算法，每次递归调用都需要压栈，导 致栈的使用很频繁。动态规划法：由于函数Knapsack中有一个两重for循环，所以时间复杂度为。(n+l)x(m+l).空间复复杂度也 是 0 (n+l)x (m+1),即 0 (nm).回溯法：由于计算上界的函数MaxBound.y需要0(n)时间，在最坏情况下有 个右儿子结点需要计算上界，所以 解0-1背包问题的回溯法算法B

16、ackTrack所需要的计算时间为.限界分支法：在使用限界分治法时，就是使用更好的限界剪枝函数使得不必要的解被剔除，但是在最坏情况下 的解仍然是和回溯法是相同的。本算法中也是用到了计算上界的函数MaxBoundary需要0(n)的时间，而且 在最坏情况下有个结点需要计算上界，所以在最坏情况下的时间复杂度仍然为。四、运行结果递归法输出结果：动态规划法输出结果:回溯法输出结果:分枝限界法输出结果:五、分析输出结果上面测试的是每种算法在两种输入情况下得到的0-1背包问题的解。两种测试数据为:第一组：背包容量：18；物品数目：7；每个物品重量为：1124896每个物品价值为：78812134第二组：背

17、包容量：50；物品数目：10；10；14o每个物品重量为：81224166每个物品价值为：343256675493532 45211819；564670o四种实现的算法中，只有回溯法没能够得到预期的最优解。(但是可能是算法设计时的问题，其实回溯法是穷举法的变形，肯定能够得到最优解的，这里是我设计函数的问题。从递归法的输出可知，它的结 果就是我们想要的最优解)。从时间复杂度和空间复杂度分析可知，动态规划法的时间复杂度是最小的， 但是同时它的空间复杂度又是最大的。这里就可以看出在设计算法的过程中要考虑它们的平衡问题。在时 间要求比拟快的情况下，我们就可以选择动态规划法；在空间要求比拟高时，我们就可

18、以使用穷举法或是 分枝限界法等其他改进的穷举法。各种算法在解背包问题时的比拟如下表所示：算法名称 时间复杂度 优点 缺点 改进穷举法递归方程求解速度快可以作为启发回溯法 最优解 分枝限界法 最优解速度慢速度慢改进剪枝优化限界函数最优解速度慢剪枝递归法最优解空间消耗大用数组存动态规划法最优解 速度慢贪心法不一定是最优解从计算复杂性理论看，背包问题是NP完全问题。半个多世纪以来，该问题一直是算法与复杂性研 究的热门话题。通过对0-1背包问题的算法研究可以看出，回溯法和分枝限界法等可以得到问题的最优解, 可是计算时间太慢；动态规划法也可以得到最优解，当时，算法需要的计算时间，这与回溯法存在一样 的缺点一一计算速度慢；采用贪心算法，虽然耗费上优于前者，但是不一定是最优解。目前，以上几种方 法中回溯法、动态规划法、贪心法都广泛地应用到不同的实际问题中，并在应用中不断地改进。