《背包问题的多种解法》由会员分享，可在线阅读，更多相关《背包问题的多种解法（14页珍藏版）》请在金锄头文库上搜索。
1、一、问题描述0/1 背包问题:现有 n 种物品，对 1,说明第 n 个物品被),(WnC),(WnC), 1(WnC装入了背包中，前 n-1 个物品被装入容量为的背包中；否则，第 n 个物品没有装nwW 入背包中，前 n-1 个物品被装入容量为 W 的背包中。依此类推，直到确定第一个物品是否被装入背包为止。由此，我们可以得到如下的函数：. ), 1(),(, 1), 1(),(0 jiCjiCwjjjiCjiCxii根据动态规划函数，用一个的二维数组 C 存放中间变量，表) 1() 1(WnjiC示把前 i 个物品装入容量为 j 的背包中获得的最大价值。设物品的重量存放在数组 wn中，价值存放
2、在数组 vn中，背包的容量为 W，数组存放迭代的结果，数组 xn存放装入背包的物品，动态规划解 0-1 背包 11WnC问题的源代码在文件夹动态规划法中。回溯法分析：用回溯法解 0_1 背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。设 r 是当前剩余物品价值总和；cp 是当前价值；bestp是当前最优价值。当 cp+rbestp 时，可剪去右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由
3、此得到的价值是右子树中解的上界，用此值来剪枝。为了便于计算上界，可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可。在实现时，由 MaxBoundary 函数计算当前结点处的上界。它是类 Knap的私有成员。Knap 的其他成员记录了解空间树种的节点信息，以减少函数参数的传递以及递归调用时所需要的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界函数 MaxBoundary，以判断是否可以将右子树减去。进入左子树时不需要计算上界，因为其上界与父结点的上界相同。在调用函数 Knapsack 之前，需要先将各物品依其单位重量价值从达到小排序。为此目的，我们定义了类 O
4、bjiect。其中，运算符与通常的定义相反，其目的是为了方便调用已有的排序算法。在通常情况下，排序算法将待排序元素从小到大排序。 在搜索状态空间树时，由函数 Backtrack 控制。在函数中是利用递归调用的方法实现了空间树的搜索。具体的代码见回溯法文件夹。限界分支法：在解 0-1 背包问题的优先队列式界限分支法中，活结点优先队列中结点元素 N 的优先级由该结点的上界函数 MaxBoundary 计算出的值 uprofit 给出。该上界函数在 0-1 背包问题的回溯法总已经说明过了。子集树中以结点 N 为根的子树中任一个结点的价值不超过 N.profit。因此我们用一个最大堆来实现活结点优先队
5、列。堆中元素类型为HeapNode,其私有成员有 uprofit,profit,weight,level,和 ptr。对于任意一个活结点N，N.weight 是活结点 N 所相应的重量；N.profit 是 N 所相应的价值；N.uprofit 是结点 N 的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为 bbnode。在分支限界法中用到的类 Knap 与 0-1 背包问题的回溯法中用到的类 Knap 很相似。他们的区别是新的类中没有了成员变量 bestp，而增加了新的成员 bestx。Bestxi=1,当且仅当最优解含有物品 i。在类 Knap 中有四个函数：（1）上界函数 Ma
6、xBoundary(),计算节点所对应价值的上界；（2）函数 AddLiveNode()是将一个新的活结点插入到子集树和优先队列中；（3）函数 MaxKnapsack()实施对子集树的优先队列式分支界限搜索。其中假定物品依其单位价值从大到小已经排好序。相应的排序过程会在算法的预处理部分完成。算法中 E 是当前扩展结点；cw 是该结点的重量；cp 是该结点的价值；up 是价值上界。算法的 while 循环不断扩展结点，直到子集树的一个叶结点成为扩展结点为止。此时优先队列中所有活结点的价值上界均不超过该叶结点的价值。因此该叶结点相应的解为问题的最优解。在 while 循环内部，算法首先检查当前扩展
7、结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。（4）函数 Knapsack()完成对输入数据的处理。其主要任务是将各物品依其单位重量价值从达到小排好序。然后调用函数 MaxKnapsack()完成对子集树的优先队列式分支限界搜索。具体的实现代码在文件夹分支限界法中。三、时空效率分析穷举法：对于一个有 n 个元素的集合，其子集数量为，所以，不论生成子集的算法效率有n2多高，穷举法都会导致一个的算法。)2(nO递归法：在递归法的算法体中有一个 if 判
8、断中出现了两次递归调用比较大小所以它们之间的递归关系式可以大体表示为：，其中表示递归法的时间复杂CnTnT) 1(2)()(nT度，C 是常数。求解递归方程可以知道的量级为。所以递归法解 0-1 背包)(nT)2(nO问题的时间复杂度为。递归法是耗费空间最多的算法，每次递归调用都需要压栈，)2(nO导致栈的使用很频繁。动态规划法：由于函数 Knapsack 中有一个两重 for 循环，所以时间复杂度为 O(n+1)x(m+1).空间复复杂度也是 O(n+1)x(m+1)，即 O（nm）.回溯法：由于计算上界的函数 MaxBoundary 需要 O(n)时间，在最坏情况下有个右儿)2(nO子结点
9、需要计算上界，所以解 0-1 背包问题的回溯法算法 BackTrack 所需要的计算时间为.)2(nnO限界分支法：在使用限界分治法时，就是使用更好的限界剪枝函数使得不必要的解被剔除，但是在最坏情况下的解仍然是和回溯法是相同的。本算法中也是用到了计算上界的函数MaxBoundary 需要 O(n)的时间，而且在最坏情况下有个结点需要计算上界，所)2(nO以在最坏情况下的时间复杂度仍然为。)2(nnO四、运行结果递归法输出结果：动态规划法输出结果：回溯法输出结果：分枝限界法输出结果：五、分析输出结果上面测试的是每种算法在两种输入情况下得到的 0-1 背包问题的解。两种测试数据为：第一组：背包容量
10、：18； 物品数目：7；每个物品重量为：11 2 4 8 9 6 10；每个物品价值为：7 8 8 12 13 4 14。第二组：背包容量：50； 物品数目：10；每个物品重量为： 8 12 24 16 6 9 35 21 18 19；每个物品价值为： 34 32 56 67 54 32 45 56 46 70。四种实现的算法中，只有回溯法没能够得到预期的最优解。 （但是可能是算法设计时的问题，其实回溯法是穷举法的变形，肯定能够得到最优解的，这里是我设计函数的问题。从递归法的输出可知，它的结果就是我们想要的最优解） 。从时间复杂度和空间复杂度分析可知，动态规划法的时间复杂度是最小的，但是同时它
11、的空间复杂度又是最大的。这里就可以看出在设计算法的过程中要考虑它们的平衡问题。在时间要求比较快的情况下，我们就可以选择动态规划法；在空间要求比较高时，我们就可以使用穷举法或是分枝限界法等其他改进的穷举法。各种算法在解背包问题时的比较如下表所示：算法名称时间复杂度优点缺点改进穷举法)2(nO最优解速度慢剪枝递归法)2(nO最优解空间消耗大用数组存动态规划法)(nmO最优解速度慢递归方程求解贪心法)log(2nnO不一定是最优解速度快可以作为启发回溯法)2(nnO最优解速度慢改进剪枝分枝限界法)2(nnO最优解速度慢优化限界函数从计算复杂性理论看，背包问题是 NP 完全问题。半个多世纪以来，该问题一直是算法与复杂性研究的热门话题。通过对 0-1 背包问题的算法研究可以看出，回溯法和分枝限界法等可以得到问题的最优解，可是计算时间太慢；动态规划法也可以得到最优解，当时，算法需要的计算时间，这与回溯法存在一样的缺点计算速度慢；nm2)2(nnO采用贪心算法，虽然耗费上优于前者，但是不一定是最优解。目前，以上几种方法中回溯法、动态规划法、贪心法都广泛地应用到不同的实际问题中，并在应用中不断地改进。
