背包问题的算法设计与分析研究

摘要：背包问题是算法设计分析中的经典问题，本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析，给出具体算法设计和实现过程，并以具体实例详细描述不同方法求解问题解时算法基本思想，总结三种方法实现的优缺点并得出结论。

关键词：背包问题；贪婪法；动态规划法；时间复杂度

中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)25-1534-02

Study on Algorithm Design and Analysis of Knapsack Problem

SUN Hong-li

(Computer Science Department, Shangqiu Normal University, Shangqiu 476000, China)

Abstract: The knapsack problem is a classical question in the area of algorithm design and analysis, in this paper greedy method, the dynamic programming method and the recursion method are used separately to solve the knapsack problem, 0-1 knapsack problem and the simple 0-1 knapsack problem, and to design the algorithm, to discuss the time complexity. Algorithm design and realization process is given, and with example algorithm basic thought to describe different solution is introduced, and the conclusion is gotten by summarizing the goods and shortcoming of three methods.

Key words: knapsack problem; greedy method; dynamic programming method; time complexity

1 引言

算法是计算机科学的核心，也是程序设计的关键，对算法的研究是通过程序来实践的，算法+数据结构=程序，此经典公式表明有了算法，加上合适的数据结构，用高级语言进行实现就可以得到程序。那么要解决背包问题，首要的前提就是设计出好的算法，想求得背包问题的解，就要先设计出算法。本文采用三种方法来对背包问题进行算法设计，并分析其时间复杂度，进而得出结论。

2 背包问题描述

背包问题是整数规划中的一类特殊问题，在现实生活中具有广泛应用，如能提出求解此问题的有效算法，则具有很好的经济价值和决策价值，如物流公司的货物发配问题，集装箱的运载问题，如何才能获得最大利润。

问题的一般描述是：旅行者背包登山，背包的最大承重为M，现有n个物品可供选择装入背包，第i个物品重量为wi，价值为pi，假定物品i的一部分xi（0≤xi≤1）放入背包，获得价值为xipi，由于背包最大承重为M，要求装入物品总质量不过超过M，问旅行者应该如何选择物品装入背包，使得装入物品的价值总和达到最大值。

背包问题的数学描述如下：要求找到一个n元向量(x1,x2,…xn)，在满足约束条件：■情况下，使得目标函数max∑xipi，其中，1≤i≤n;M>0;wi>0;pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解。

3 局部优先策略的贪婪法求解背包问题

采用贪婪法求解问题的最优解核心是选择合适的优化测度，下面以一个背包问题的具体实例来说明求解思想。已知：n=3，w=(10,25,30)，p=(60,50,90)，M=30，求如何装包可得到最大价值。

分析：如果从剩余的物品中每次都选取当前价值最大的来装入的话，利用价值优先测度，不能保证获得最优解，也就是说如果优化侧度的选取只考虑价值是不行的；如果每次都选择背包耗费最小的物品装入的话，利用质量最小作为优化测度，同样也不能保证得到最优解，只考虑质量同样无法得到最优解；最后我们同时考虑价值和质量，以单位质量价值大的物品首先装入，以此作为优化测度，就可以保证背包问题获得最优解。上面的例子求解结果如下：最大价值为120，解向量为（1，0，2/3）。其求解过程可以简单概括如下，首先对所有物品的单位质量价值按非升序排列，然后一个个考虑物品，装入物品后要修正背包的当前承重及已获得价值，如果背包的当前承重不足以装入整个物品时，可以装入物品的一部分保证背包装满而获得最大价值。由此利用局部最优策略求解背包问题得到的局部最优解肯定是全局最优解。

采用贪婪法局部优先策略算法时间复杂度是T(n)=O(n2)。首先我们对物品单位质量的价值非升序排列，采用冒泡法实现，执行时间为T1(n)=(n-1)+(n-2)+…+1=n(n+1)/2；从排好序的物品中选取加入解向量，最大执行n次T2(n)=O(n)，故贪婪法总的时间耗费为：T(n)=T1(n)+T2(n)=O(n2)。

如果对背包问题进行扩展，再装入物品时只允许全装或者不装，不允许装入物品的部分，也就是xi=1或者xi=0。此时成为0-1背包问题。那么对0-1背包问题，贪婪法可以求得最优解吗？

答案是否定的，还以上面的实例说明，采用贪婪法求的解向量为（1，0，0），最大价值为60，很明显，（0，0，1）优于前者，最大价值为90。要求0-1背包问题的最优解就需要采用全新的算法思想，下面具体说明。

4 最优化原理的动态规划法求解0-1背包问题

动态规划法的核心基础是最优化原理，它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：

①分析最优解的结构：最有子结构性质；

②建立递归方程；

③计算最优值；

④构造最优解。

下面用动态规划法求解0-1背包问题。首先此问题具有最优子结构性质。简单说明如下：设(y1,y2,…,yn)是最优解，则(y2, …,yn)是对应子问题的一个最优解：max■ pixi，■

采用反证法说明：假设(y2, …,yn)不是对应子问题的最优解，那么必定存在最优解，令 (z2,…,zn)是对应子问题的一个最优解。由上述假设得到， ■zipi> ■yipi，并且w1y1+ ■ziwi≤M在■zipi> ■yipi两边同时加上p1y1，得到 ■zipi+p1y1> ■yipi+p1y1，合并w1y1+ ■ziwi≤M，可得出(y1,z2,…,zn)优于(y1,y2,…,yn)，推出矛盾，也即假设不成立。符合最优子结构性质。

根据最优子结构性质可以推出递归方程。引入符号v(i,j)表示i个物品当前背包承重为j时可以获得的最大价值，要求得i个物品可以获得最大价值要考虑第i个物品质量和当前背包承重大小关系，背包可以容纳第i个物品的话，有装入和不装两种情况，表示为v(i-1,j-wi)和v(i-1,j)，如果第i个物品质量大于背包当前承重，则只有不装，即v(i-1,j)。由此可以得出关于解的递归方程如下：

■

根据递归方程，可以求得0-1背包问题的最大价值和解向量，还以上面的实例说明求解过程。

■

故得到：v(1,30)=60;v(2,30)=60;v(3,30)=90；X=（0，0，1），从这个求解过程可得动态规划法肯定可以得到0-1背包问题的最优解。

动态规划法算法执行时间为n*a*b次循环，每次循环都要执行比较运算，算法完成所需总是件为cn2，故时间复杂度为

T(n)=O(n3)。

如果对0-1背包问题的求解目标进行限制，求如何装包可以使得装入物品的重量总和恰好是M。那么问题就不再是最优化问题，称为简单的0-1背包问题。显然，用贪婪法或动态规划法都无法求得此问题的解向量，这时需要用到递归法来求解。

5 递归法求解简单0-1背包问题

简单0-1背包问题可以描述为：现有n个物品，第i个物品质量为wi，有一个可容物品最大质量为M的背包，如何从n件物品中选取出若干件装入使得放入背包的质量之和正好为M。

由于0-1背包问题对第i件物品要么装入，要么不装，故问题可能有解，也可能无解。采用布尔函数表示问题。Knap(i,j)其中i表示物品个数，j表示背包当前容量。如果问题有解函数值为true，否则为false。

先取第n个物品装入，如果wn=M,knap(n,M)=true；

如果wn1,knap(n,M)= knap(n-1,M-wn)有解可行，否则转化为knap(n,M)= knap(n-1,M)；

如果wn1,knap(n,M)= knap(n-1,M)。

递归算法的执行时间是那n2次调用，每次调用完成一次比较和一次栈运算，算法完成总时间是2n2，时间复杂度为T(n)O(n2)。

6 结论

这三种算法都在c语言环境下得到验证，运行结果证明了算法设计是可行的，正确的。通过对背包问题、0-1背包问题与简单0-1背包问题的算法设计及时间复杂度分析可以看出，无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法，前者的时间复杂度低于后者，从耗费上而言优于后者，但后者的实现算法可读性要优于前者。

参考文献：

[1] M.H.Alsuwaiyel.算法设计技巧与分析[M].北京:电子工业出版社，2004.

[2] 任瑞证,严蔚敏.整数背包问题的应用及其算法研究[J].小型微型计算机系统,2001,22(2):204-206.

[3] 刘西奎,李艳,许进.背包问题的遗传算法求解研究[J].华中科技大学学报（自然科学版）,2002,30(6):89-90.