解0-1背包问题的动态规划算法及其两次改进.docVIP

 解 0-1 背包问题的动态规划算法及其两次 改进 许薇，周继鹏** 5 10 15 20 （暨南大学信息科学技术学院，广州 510632） 摘要：给出了用动态规划算法解决 0-1 背包问题的证明，分析了动态规划算法解决 0-1 背包 问题的不足和性能。然后，针对用该动态规划算法解决 0-1 背包问题的不足，对它进行改进， 改进后的算法称之为 IKP 算法。为了降低 IKP 的空间复杂度，在 IKP 上运用分治策略，得到 的算法称之为 DKnapsack 算法。分析表明，DKnapsack 比起 IKP 在运行时间和资源耗费上都 有很大的优势。而且，相比其它解 0-1 背包问题的算法，DKnapsack 也具有很好的时间复杂 度。最后，用实验论证了理论的正确性。 关键词：0-1 背包问题；动态规划；分治策略；改进 中图分类号：TP311 Using Dynamic Programming To 0-1 Knapsack Problem Xu Wei, Zhou Ji Peng (College of Information Science and Technology, JiNan University, GuangZhou 510632) Abstract: This paper gave proof for using dynamic programming algorithm to solve 0-1 knapsack problem, analyzed drawback and the performance of this algorithm. Then, based on the feature of 0-1 knapsack problem, this paper improved the algorithm. It was called Algorithm IKP. Finally, in order to reduce the spatial complexity of Algorithm One, this paper adopted divided-and-conquered strategy, called Algorithm DKnapsack. Analysis shows that Algorithm DKnapsack has a great advantage over Algorithm IKP in running time and resource cost. Keywords: 0-1 knapsack problem; Dynamic programming; Divided-and-conquered; Improvement 25 0 引言 经典的 0-1 背包问题描述如下：给定具有 n 个物品的物品集和具有容量 c 的背包，其中 每个物品具有价值 p j 和重量 w j ，要求选取物品集的一个子集，使得它们的总价值达到最大 并且重量之和小于等于背包容量 c。我们引进二元变量 x j ，如果选取了物品 j 则 x j = 1，否 30  则 x j = 0 。 用 数 学 表 达 式 描 述 这 个 问题 ： maximize z?? n ≤ c ，其中 x j?∈{0,1} , j?∈{1, 2,..., n} j j j??1 n j??1  j  j  ，且满足约束： 动态规划是解决组合优化最古老的方法之一，尤其是在背包类型的问题上。被忽略了一 段时间以后，这个领域上又出现了若干解决背包问题的新颖方法，见参考文献[1, 2, 3]。在 这里，我们首先介绍用动态规划方法解决背包问题，然后基于 0-1 背包问题的特点，给出一 35 个改进方法。最后，为了减少程序使用的内存空间的考虑，我们再对这个改进方法做进一步 改进。 作者简介：许薇，(1987-)，女，学生，主要研究方向:无线网络。 通信联系人：周继鹏，(1962-)，男，教授，主要研究方向:无线网络。E-mail: tjpzhou@jnu.edu.cn -1-  1 背包问题的动态规划算法 1.1 最优子结构 0-1 背包问题具有最优子结构性质。设（x1, x2 ,..., xn ) 是所给 0-1 背包问题的一个最有解， 40 则（x2 ,..., xn ) 是下面相应子问题的一个最优解： maximize z′??  n i? 2 ??∑ wi xi?≤ c?? w1 x1 x?∈ {0,1}, 2?≤ i?≤ n ? 若不然，设 ( z2 , z3 ,..., zn ) 是上述子问题的一个最有解，而（x2 ,..., xn ) 不是它的最优解。 由此可知，