求解0－1背包问题的两种方法的分析与比较

刘建芹，王英杰

（石家庄信息工程职业学院，河北 石家庄 050035）

1 引言

背包问题（knapsack problem，KP）是计算机科学中典型的NP－hard问题，最早由Dantzing［1］于20世纪50年代首先提出并研究。KP问题具有很高的理论与应用价值，在投资决策、预算控制、项目选择、资源分配和货物装载等方面有着非常重要的应用。由于KP问题的NP－hard性，使得该问题的求解比较困难，常见求解算法有两类：即确定性算法和非确定性算法。例如动态规划法和分支限界法［2，3］是求解KP问题的两种确定性算法，而求解 KP的模拟退火算法［4］、遗传算法［5］、蚁群算法［6］、粒子群算法［7］等进化算法通常被认为是非确定性算法。目前，利用进化算法求解KP问题的研究成果丰富，对利用各种进化算法求解KP问题的比较研究也非常多，因此本文主要研究动态规划法和基于贪心策略的近似算法求解KP问题，比较它们在求解速度与求解质量方面的优劣。

在第2节中，给出0－1KP问题的数学模型，并介绍了一种可快速求解的2－近似算法；在第3节给出了利用动态规划法求解KP问题的完整算法描述，讨论了其复杂度；随后，通过仿真计算和复杂度分析对两种方法进行了比较，并利用3个较大规模实例与文献［7］中的GDPSO进行比较。最后，总结全文并展望下一步的工作。

2 0－1KP问题及其近似算法

背包问题的数学描述［1，5］为：设n个物品的价值集为C＝ ｛c1，c2，…，cn｝，重量集为W＝ ｛w1，w2，…，wn｝，ci，wi∈Z＋，1≤i≤n，Z＋为正整数集；又设背包载重为M∈Z＋，满足条件n）。求解向量X＝ （x1，x2，…，xn）∈ ｛0，1｝n，使得

其中，当xi＝1时表示第i个物品装入背包；当xi＝0时表示第i个物品不装入背包。一般地，称背包问题中物品数n为问题的规模。

在文献［8］中，利用贪心策略给出了一种求解0－1KP问题的近似算法，即首先根据物品的价值重量比由大到小的顺序对n个物品进行排序，然后从价值重量比大的物品开始依次将物品装入背包，直到出现某物品的重量超过背包的剩余重量为止，此时所装入背包中的物品即为0－1KP问题的一个近似解。

若设n个物品的价值重量比为ci／wi（1≤i≤n），将n个物品按其价值重量比排序。设T与S是两个临时变量，分别存放背包剩余载重和装入背包物品的价值之和，X［1..n］为所求近似解对应的解向量，则求解0－1KP问题的近似算法［8］（以下记为GAKP）描述如下：

算法1 GAKP（C［1..n］，W［1..n］，M）

1Sort n items in descending order of value／weight，namely，c1／w1≥c2／w2≥…≥cn／wn；

2 Forj＝1 tonDoX［j］←0；

3T←M；S←0；i←1；

4 Whilew［i］≤Tandi≤nDo

5X［i］←1；S←S＋c［i］；

6T←T－w［i］；i←i＋1；

7 EndWhile

8 Return（X［1..n］，S）

显然，算法1输出的X［1..n］即为0－1KP问题的近似解，S是该解所对应装入背包物品的价值之和（即近似最优值）。GAKP的算法复杂度为O（nlgn），而且已经证明其近似比为2［8］。实际上GAKP的贪婪特性还不够充分，文献［7］在利用粒子群优化算法求解0－1KP问题时注意到这一问题，对贪心策略进一步作了有效改进。下面将利用这种改进的贪心策略，给出一种求解0－1KP问题的改进近似算法。

设n个物品按其价值重量比排序后的序号依次存放在一维数组A［1..n］中，即A［1］≥A［2］≥…≥A［n］。又设X［1..n］为所求得的解向量，T与S是两个临时变量，分别存放装入背包的物品的重量之和与价值之和，则求解0－1KP问题的改进近似算法（Improved approximation for 0－1Knapsack Problems，IAKP）的伪代码表示如下：

算法2 IAKP（C［1..n］，W［1..n］，M）

1Sortnitems in descending order ofci／wi，and place these indices inA［1..n］in turn.

2 Forj＝1 tonDoX［j］←0；

3T←0；S←0；

4 Forj＝1 tonDo

5T←T＋W［A［j］］；

6 IfT≤MthenX［j］←1；S←S＋C［A［j］］；

7 ElseT←T－W［A［j］］；

8 EndFor

9 Return（X［1..n］，S）

显然，算法2求得的X［1..n］为0－1KP问题的近似最优解，S是相应的近似最优值。

令XIAKP为IAKP的求得0－1KP问题的近似解，XGAKP为GAKP所求得的近似解。显然有f（XIAKP）≥f（XGAKP），即XIAKP对应的近似最优值优于XIAKP的，这是因为当GAKP执行第4步时，若条件不满足则结束求解；但是对于IAKP，即使w［i］≤Tandi≤n不成立，仍然会继续检查i＋1及其之后的项，从而仍有可能继续向背包中装入物品。因此，IAKP的近似比必然不会超过GAKP，所以IAKP也是2－近似算法。此外，IAKP的复杂度也为O（nlgn）。

3 利用动态规划法求解KP问题

动态规划法（Dynamic programming，DP）是一种求解KP问题的确定性算法，也是一种非常有效的方法，对于规模不大的0－1KP问题其求解速度相对较快。利用DP求解0－1KP问题时，首先要建立子问题最优值之间的递归关系式，然后利用此关系式由小到大依次求子问题的最优值，最终得到的即为原问题的最优值，并利用此过程中的信息求得0－1KP问题的最优解。

记0－1KP（i，j）是物品数为i背包载重为j的子问题，令V［i，j］（1≤i≤n，1≤j≤M）表示从物品1，2，…，i中选择装入背包载重为j的0－1KP（i，j）子问题的最优解，C［1..i］与W［1..i］分别为该子问题中物品的价值集与重量集。又令V［i，0］＝V［0，j］＝0（其中0≤i≤n且0≤j≤M），于是相邻子问题的最优值之间的递推关系为：

显然，0－1KP（n，W）问题即为原始的0－1KP问题，其最优值为V［n］［M］。根据（2）式计算V［n］［M］的算法（简记为preDPKP）伪代码描述如下：

算法3 preDPKP （C［1..n］，W［1..n］，M）

1 Forj＝0toMDoV［0］［j］←0；

2 Fori＝0tonDoV［i］［0］←0；

3 Fori＝1 tonDo

4 Forj＝1 toMDo

5V［i，］［j］←V［i－1］［j］；

6 IfC［i］≤jandV［i］［j］＜V［i－1］［j－C［i］］＋W［i］then

7V［i］［j］←V［i－1］［j－C［i］］＋W［i］；

8 Endfor

9 Endfor

10 ReturnV［n］［M］

在算法3中，若步骤7被执行则说明物品i装入了背包中，注意到此时V［i］［j］＞V［i－1］［j］，因此利用V［i］［j］的V［i－1］［j］变化容易求得0－1KP问题的最优解。于是，在算法3的基础上，求解0－1KP问题最优解与最优值的动态规划算法（Dynamic programming for knapsack problem，DPKP）的伪代码描述为：

算法4 DPKP（C［1..n］，W［1..n］，M）

1 Fori＝1 tondoX［i］←0；

2S←preDPKP（C［1..n］，W［1..n］，M）；

3i←n；j←M；

4 Whilei＞0do

5 IfW［i，j］＞W［i－1，j］thenX［i］←1andj←j－C［i］；

6i←i－1；

7 Endwhile

8.Return（X［1...n］，S）.

算法4的时间复杂度主要取决于步骤2，因此算法4的时间复杂度为O（nM）。注意到logM为M的输入规模，因此算法4实际上是一个伪多项式时间算法。尽管如此，由于它能够求得0－1KP问题的精确解，因此在实际应用中利用算法4求解规模不大的0－1KP问题仍然是主要方法之一。

4 仿真计算与比较

下面首先从理论上分析求解0－1KP问题的近似算法IAKP和精确算法DPKP的优缺点，然后利用规模为50，100和200的3个较大规模的0－1KP实例，通过仿真计算结果进行验证，并与文献［7］中的进化算法GDPSO进行比较。

显然，近似算法IAKP往往求得0－1KP问题的近似解，而DPKP总是求得问题的精确解。但是，IAKP的时间复杂度为O（nlgn），是多项式时间算法，而DPKP的时间复杂度为O（nM）＝O（n2logM），是一个伪多项式时间算法，即当M的值较大时，耗费的运行时间非常多。因此对于规模与M均不大的0－1KP实例，利用DPKP求解是首选算法；但对于规模与M均很大的0－1KP实例，在对解的精度要求不是非常高的情况下，利用IAKP求解是适宜的。

对于0－1KP实例1－3，仿真计算所使用的硬件环境为DELL Pentium（R）4－CPU1.69GHz微型计算机，128M内存；操作系统为Windows XP，并采用VC＋＋6.0进行编程实现。计算结果见表1，其中给出了各算法所求得的最优解（或近似最优解）对应的解向量、对应的最优值（或近似最优值）（用“价值／重量”表示）以及计算各实例所耗费的时间（单位：s）。对于实例1－3，GDPSO的迭代次数分别为50，100，200，耗费时间为20次计算的平均时间，并取20次计算的最好结果。GDPSO的其他参数设置同文献［7］中。

实例1［9］规模为50的0－1KP实例，其中物品的价值集为｛220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，72，70，69，66，65，63，60，58，56，50，30，20，15，10，8，5，3，1｝；重量集为｛80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，50，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，10，4，4，2，1｝；背包载重为1000。

实例2 规模为100的0－1KP实例，其中物品的价值集为｛783，777，766，759，745，732，732，732，731，730，714，712，711，696，689，687，669，657，656，641，635，632，632，616，612，605，603，587，583，571，570，556，549，549，544，537，530，523，521，516，510，506，505，504，498，496，496，489，470，458，447，446，434，431，424，422，420，419，415，412，403，400，400，385，382，367，352，339，330，312，310，297，283，283，280，275，268，262，247，237，223，215，192，185，176，156，154，151，131，131，131，125，118，106，82，79，66，61，57，56｝；重量集为｛482，233，446，398，387，521，17，340，168，237，442，260，40，492，396，162，223，273，324，304，171，342，457，227，250，227，226，241，441，372，314，462，132，207，360，370，41，392，384，155，217，150，139，354，195，325，18，166，437，270，70，4，36，335，467，426，25，12，425，425，429，186，383，391，133，465，508，44，348，231，522，320，431，158，382，310，12，412，371，273，152，125，123，406，284，393，295，152，85，387，436，25，352，249，215，294，143，40，40，328｝；背包载重为17656。

实例3 规模为200的0－1KP实例，其中物品的价值集为｛238，381，506，354，476，916，175，841，571，236，554，641，927，811，169，141，1086，1084，901，685，1038，230，381，512，1090，860，189，243，912，772，703，422，797，1074，426，863，155，213，999，692，856，629，142，1038，1065，163，127，890，781，138，839，635，507，441，224，819，1077，138，950，1040，882，332，126，309，672，804，485，999，1021，156，1059，708，437，570，786，359，150，736，847，471，621，640，586，107，373，361，216，450，781，402，753，709，452，252，192，891，1002，549，751，758，280，527，812，514，833，693，387，907，267，467，521，914，709，878，270，510，1008，284，676，245，284，398，958，967，870，384，752，811，455，312，1016，165，665，132，242，163，494，857，368，1010，629，118，261，1078，1073，172，947，1080，505，528，651，465，596，700，852，356，911，401，582，540，819，719，200，265，630，200，855，128，991，346，278，425，376，1076，906，247，268，1056，597，679，884，635，311，602，1052，901，645，440，479，203，585，973，1014，424，742，133，558，188，486，113｝；重量集为｛139，282，407，255，377，817，76，742，472，137，455，542，828，712，70，42，987，985，802，586，939，131，282，413，991，761，90，144，813，673，604，323，698，975，327，764，56，114，900，593，757，530，43，939，966，64，28，791，682，39，740，536，408，342，125，720，978，39，851，941，783，233，27，210，573，705，386，900，922，57，960，609，338，471，687，260，51，637，748，372，522，541，487，8，274，262，117，351，682，303，654，610，353，153，93，792，903，450，652，659，181，428，713，415，734，594，288，808，168，368，422，815，610，779，171，411，909，185，577，146，185，299，859，868，771，285，653，712，356，213，917，66，566，33，143，64，395，758，269，911，530，19，162，979，974，73，848，981，406，429，552，366，497，601，753，257，812，302，483，441，720，620，101，166，531，101，756，29，892，247，179，326，277，977，807，148，169，957，498，580，785，536，212，503，953，802，546，341，380，104，486，874，915，325，643，34，459，89，387，14｝；背包载重为60507。

表1 IAKP、DPKP与GDPSO的计算结果比较

从表1中可以看出：当的0－1KP实例规模和背包载重较小时，DPKP能够耗费较少的时间求得最优解，但是随着问题规模和背包载重的增大，DPKP所耗费时间的增长幅度非常大，求解速度明显比IAKP慢。而随着问题规模和背包载重的增大，IAKP耗费的时间虽然也逐渐增加，但其增加的趋势几乎是线性的，增速非常缓慢；同时，虽然IAKP不一定能够求得问题的最优解，但其求解质量与求解速度相对于进化算法GDPOS而言具有明显的优势。

5 结束语

本文给出了求解0－1KP问题的改进近似算法IAKP，并与动态规划法DPKP进行了分析和比较，从仿真计算结果来看，虽然IAKP往往只能求得问题的近似解，但其求解速度远比DPKP更快，而且通过与进化算法GDPOS的对比还表明IAKP的求解结果更接近于最优解，而且耗费时间也比GDPOS少。所以，对于大规模且背包载重很大的0－1KP实例，在对解的精度要求不高时，利用IAKP的求解是非常适宜的。今后将进一步研究分枝限界等方法求解0－1KP问题，探讨更优的求解方法。

［1］ Kiefer J.On large deviations of the empiric of vector chance variable and a law of the iterated logarithm［J］.Pactific J.Math，1961，11（3）：649－660.

［2］ Sedgewick R.and Flajolet P.An introduction to the analysis of algorithms［M］.Boston：Addison Wesley Publishing Company.1999.

［3］ Alsuwaiyel M.H.Algorithms design techniques and analysis.World Scientific Publishing Company，2003.

［4］ 康立山，谢云，等.非数值并行算法（一）—模拟退火算法［M］.北京：科学出版社，2003.

［5］ 周明，孙树栋.遗传算法原理及其应用［M］.北京：国防工业出版社，2001.

［6］ Marco Dorigo，Thomas Stutzle.Ant colony optimization［M］.MIT press，2004.

［7］ 刘建芹，贺毅朝，顾茜茜.基于离散微粒群算法求解背包问题研究［J］.计算机工程与设计，2007，28（13），3189－3191，3204.

［8］ 张德富.算法设计与分析（高级教程）［M］.北京：国防工业出版社，2007.

［9］ 徐宗本.计算智能—模拟进化计算［M］.北京：高等教育出版社，2005.