Abstract： Knapsack problem is a typical NP-C problem as well as algorithm design and analysis of the classical problems in the common field of operations research. It is very important to study the solution of the problem, whether in theory or in practice. After some research, a lot of classical methods solving this problem have been come up with ,and the exploration of this issue and applied research has been ongoing. Under the guidance of advanced theory, there are distinctive features such as scientific, efficient, economic, flexible and convenient features in solving the 0-1 knapsack problem .
So to solve the knapsack problem, the first premise is to design a good algorithm.To seek the solution of knapsack problem, it is necessary to design algorithms using dynamic programming at first. In this paper, four methods such as dynamic programming, backtracking, branch - Bound method and genetic algorithm respectively aiming at knapsack problem ,0-1 knapsack problem and a simple 0-1 knapsack problem carry out the algorithm design and analysis of time complexity, and give the specific algorithm design and implementation of the process.And descript detailedly the basic idea of algorithm by using specific examples in solving the issue with different ways .And then aiming at solving the 0-1 knapsack problem , compare four algorithms in detail and summarize the advantages and disadvantages of realization of four methods and reach a conclusion.How to apply the knapsack problem into the practical, and to design targeted for the practical algorithms of solving 0-1 Knapsack Problem and to solve the practical problems very well, is an area of computer workers’ constantly thinking and study.
Key words：0-1 knapsack problem dynamic programmi backtracking branch - Bound method genetic algorithm
2
1 绪论
1.1问题的提出及研究意义
0-1背包问题是计算机科学中的一个非常经典的优化问题。也是被证明了的NP难度问题。它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放到背包中来加密消息。背包中的物品中重量是公开的，所有可能选择的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。围绕这个问题的求解方法很多，比如贪婪算法、动态规划、分枝限界、回溯法、遗传算法等等。其中回溯法是常见的一种求解方法。
多年来，背包问题吸引了许多理论和实际工作者对此问题作深入的研究，在理论上，尽管背包问题的结构简单，但它却具有组合爆炸的性质，在实际应用中，许多工业问题都可以用背包问题来描述求解，如资金运算、货舱装载、存储分配等都是其典型的应用例子。如何将背包问题应用于实际问题中，并很好地解决实际问题，是计算机工作者不断思索、研究的一个领域。
1.2 0-1背包问题的算法研究的分析
0-1背包问题的算法研究主要是通过算法设计与分析知识，设计解决相关问题的尽可能高效的算法并程序实现，而且能够分析算法的复杂性，通过实验进一步领会各种算法设计技术的基本原理，掌握算法设计和分析方法，提高算法设计与分析的应用能力。
0-1背包是一类很典型的优化问题,研究它有很重要的实际意义，这不仅是由于它结构简洁，可以作为子问题为研究更复杂的问题奠定理论基础，有很高的理论研究价值，而且由于它是许多实际工程应用问题的种通用化描述，在很多实际问题当中有着非常广泛的应用背景，例如项目决策等。他是最基本的背包问题，即对一个物体要么选用，要么就抛弃，不能将一个物体再继续细分的情况。它包含了背包问题中设计状态、方程的最基本思想，在经济管理、资源分配、投资决
3
策、装载设计等领域有着重要的应用价值。在计算理论中属于NP-C完全问题，其计算复杂度，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。
1.3课题的主要研究内容
1.3.1背包问题的描述
背包问题是整数规划中的一类特殊问题，在现实生活中具有广泛应用。如果能提出求解此问题的有效算法，则具有很好的经济价值和决策价值。
问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品莺量为wi，价值为pi，假定物品i的一部分xi(0?xi?1)放人背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。
背包问题的数学描述如下：要求找到一个n元向量(x1，x2?xn)，在满足约
??xw?M束条件：??ii情况下，使得目标函数max?xi?0?x?1i?p，其中，1?i?n；M>0；
iwi>0；pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解[1]。 1.3.2 0-1背包问题
① 0-1背包问题的提出
给定n 种物品和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。
② 问题符号化
0-1背包问题的符号化表示是，给定M>0， w i >0， pi >0，1?i?n ，要求找到一个n元0-1向量向量(x1，x2?xn)， X i =0 或1 , 1?i?n, 使得
?xwii?M ，而且?xip达到最大
i[2]
。
4
2 0-1背包问题的实现
2.1 0-1背包问题在动态规划中的实现
2.1.1 动态规划的基本原理与分析
动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：
①分析最优解的结构：最有子结构性质； ②建立递归方程； ③计算最优值； ④构造最优解[4]。
动态规划算法的每一步决策都是根据前一步的状态参量来决定这一步状态参量的设置，也就是说，从初始状态到最终状态要经过多个过程，经历不同的状态，不断地根据上一步状态决定下一状态，从而形成了一个决策序列，最终将整个问题解决，这就是典型的多段决策的特性。
由上面的动态规划法的介绍，可以看出0-1背包问题，是符合多段决策的特点和具有重叠子问题。因此，在设计0-1背包问题解决方案时，可以将整个物品放到背包的过程，看成一个取物品的过程。 2.2.2 0-1背包问题的实现
① 最优子结构性质
0-1背包问题具有最优子结构性质。设(y1，y2?yn)是所给0-1背包问题的一个最优解，则(y2，y3?yn)是下面相应子问题的一个最优解：
max?vkxkk?in
5