目 录
第一章 算法思想 ................................................. 1
1．1问题的提出.............................................. 1 1.2 贪心算法的算法思想 ...................................... 1 1.3动态规划的算法思想....................................... 2 第二章 0-1背包问题的求解........................................ 3
2.1 用贪心算法求解0-1背包问题 .............................. 3 2．2用动态规则算法求解0-1背包问题.......................... 4 第三章 算法分析及比较.......................................... 8
3.1算法分析................................................. 8 3.2贪心算法与动态规划算法的比较............................. 8 小结 ............................................................ 9 参考文献 ........................................................ 9 致谢 ........................................................... 10
0-1背包算法及其应用
马文秀,数学计算机科学学院
摘 要: 0-1 背包问题是运筹学中的著名问题,有重要的使用价值,是算法研究
的热点,目前较成熟的常用算法有贪心算法、动态规划、回溯法、分枝/限界法等。本文通过比较贪心算法和动态规划算法的联系与区别，最后重点通过动态规划方法来求解0-1背包算法
关键词: 0-1背包，动态规划，最优性原理
The Algorithm and Application of Knapsack Problem
Wenxiu Ma，College of Mathematics and Computer Science
Abstract:Zero-one Knapsack Problem, a hotspot in algorithm study, is a famous
problem of great value in operational research. Presently, Greedy direct decoding algorithm, dynamic programming, backtrack method and branch and bound method are relatively full-blown algorithms. This paper will make a comparison between Greedy direct decoding algorithm and dynamic programming, trying to find the relations and discrepancies about them. Finally, it attaches great importance to solving the Zero-one Knapsack Problem through the way of dynamic programming.
Key words: Zero-one Knapsack Problem, Dynamic Programming, the Principle of
Optimization
第一章 算法思想
背包是运筹学中的著名问题， 指背包的容量有限，将不同体积物体放入包中，放哪些物体才能使背包空间充分利用。 这个问题具体描述为：有N 种物品和一个可容纳M 重量的背包，每种物品的重量为wi，假定将物品i 的一部分xi 装入背包，得到pixi(0?xi?1,pi?0) 的收益，采用怎样的装包方法才会使装入背包的物品总效益最大呢？并且总量不能超过M。如果xi 只能取0或1，也就是说一件物品要么装入全部，要么不装入，就是0-1 背包问题。
1.1问题的提出
0-1背包问题是计算机学科中的一个经典的算法问题，也是被证明了的NP-难问题。给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0/1背包问题。
此问题的形式化描述是，给定 c>0,wi>0,vi>0, 1?i?n,要求找出一个n元0-1向量(x1,x2,………,xn), xi=0或者1， 1?i?n使得?wixi?c而且?vixi达得最大。
i?1i?1nn数学模型为：max?vixi
i?1n?n??wixi?c约定条件：?i?1
?xi?0或者1,1?i?n?背包问题分为部分背包问题和0/1背包问题两种。部分背包问题在选择物品时，可以将物品分割为部分装入背包，即贪心算法[1]
每个最优化间题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解，使优化函数取得最佳值的可行解称为最优解。
1.2 贪心算法的算法思想
贪心算法是一种不要求最优解，只希望得到较为满意解的方法。贪心方法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法常以当前情况为基础不要回溯。但是，对于某些情况。实际上有解，而该算法不能找到解。对于找不到解的情况，程序只要穷举所有可能情况，就能找到解。
在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都在一定的标准下做出一个看上去最优的决策.决策一旦做出，就不可再更改.做出贪婪决策的依据称为贪婪准则(greedycriterion)。
1
1.3动态规划的算法思想
动态规划方法建立在最优原则的基础上，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。
动态规划是解决多阶段决策过程的最优性原理，它的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，运用动态规划方法的前提是所求解问题的最优性原理需成立，求解的关键是获取各阶段间的递推关系式。 并且最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
2
第二章 0-1背包问题的求解
2.1 用贪心算法求解0-1背包问题
1.算法探讨
0/1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装人。在每一步过程中利用贪婪准则选择一个物品装人背包。一种贪婪准则为：从剩余的物品中，选出可以装人背包的价值最大的物品，利用这种规则，价值最大的物品首先被装人(假设有足够容量)，然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。
为什么上述贪心策略不能获得最优解呢?原因在于背包可用容量消耗过快。由此，很自然地启发我们用容量作为量度，让背包容量尽可能慢慢地被消耗。另一种方案是重量贪婪准则:从剩下的物品中选择可装人背包的重t最小的物品。但这种规则在一般情况下不一定能得到最优解。[2]还可以利用另一种方案，价值密度vi/wi贪婪算法，这种选择准则为:从剩余物品中选择可装人包的vi/wi值最大的物品，这种策略也不能保证得到最优解，但它是一个直觉上近似的解。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x%(x<100)之内。首先将最多k件物品放人背包，如果这k件物品重量大于c，则放弃它。否则，剩余的容量用来考虑将剩余物品按vi/wi递减的顺序装人。通过考虑由启发式产生的解法中最多为k件物品的所有可能的子集来得到最优解。 2.算法实例求解
我们给出一个实例来解释该算法的运行过程。考虑 n=4, c=11 w=[2,4,6,7] v=[6,10,12,13]
当k=0 时，背包按物品价值密度3,2,5,2,1,86的非递减顺序装入，首先将物品1 放入背包，然后是物品2，背包剩下的容量为11-2-4=5个单元，剩下的物品没有一个合适的，因此解为x=[1,1,0,0]。此解获得的价值为16。
现在考虑k=1时的贪婪启发法。就是依次验证从取定i开始的，然后按物品价值密度非递减得到的最优解。最初的子集为｛1 ｝，｛2 ｝，｛3 ｝，｛4 ｝。子集｛1｝，｛2｝产生与k=0时相同的结果，考虑子集｛3 ｝，置x3为1。此时还剩5 个单位的容量，按价值密度非递减顺序来考虑如何利用这5 个单位的容量。首先考虑物品1，它适合，因此取x1 为1，这时仅剩下3 个单位容量了，且剩余物品没有能够加入背包中的物品。从子集｛3｝开始求解得结果为x=[1,0,1,0]，获得的价值为18。从子集｛4 ｝开始，产生的解为x=[1,0,0,1]获得的价值为19。综合考虑子集大小为0 和1 时获得的最优解为［1,0,0,1］。价值为19。这个解是通过k=1的贪婪启发式算法得到的。若k=2，就是依次验证从取定i,j 开始的，然后按物品价值密度非递减得到的最优解，同时和k=1 时的解进行比较。除了考虑k<2的子集，还必需考虑子集｛1,2 ｝，｛1,3｝，｛1,4 ｝，｛2,3 ｝，｛2,4 ｝和｛3,4｝。首先从最后一个子集开始，它是不可行的，故将其抛弃，剩下的子集经求解分别得到如下结果：［1,1,0,0 ］，［ 1,0,1,0］，［1,0,0,1］，［0,1,1,0］和［0,1,0,1］，这些结果中最后一个价值为23，它的值比k=0和k=1时获得的解要高，这个答案即为k=2 启发式方法产生的结果 3算法分析
3
0-1背包算法及其应用
