求解0－1背包問題的兩種方法的分析與比較

劉建芹，王英杰

（石家莊信息工程職業(yè)學院，河北 石家莊 050035）

1 引言

背包問題（knapsack problem，KP）是計算機科學中典型的NP－h(huán)ard問題，最早由Dantzing［1］于20世紀50年代首先提出并研究。KP問題具有很高的理論與應用價值，在投資決策、預算控制、項目選擇、資源分配和貨物裝載等方面有著非常重要的應用。由于KP問題的NP－h(huán)ard性，使得該問題的求解比較困難，常見求解算法有兩類：即確定性算法和非確定性算法。例如動態(tài)規(guī)劃法和分支限界法［2，3］是求解KP問題的兩種確定性算法，而求解 KP的模擬退火算法［4］、遺傳算法［5］、蟻群算法［6］、粒子群算法［7］等進化算法通常被認為是非確定性算法。目前，利用進化算法求解KP問題的研究成果豐富，對利用各種進化算法求解KP問題的比較研究也非常多，因此本文主要研究動態(tài)規(guī)劃法和基于貪心策略的近似算法求解KP問題，比較它們在求解速度與求解質(zhì)量方面的優(yōu)劣。

在第2節(jié)中，給出0－1KP問題的數(shù)學模型，并介紹了一種可快速求解的2－近似算法；在第3節(jié)給出了利用動態(tài)規(guī)劃法求解KP問題的完整算法描述，討論了其復雜度；隨后，通過仿真計算和復雜度分析對兩種方法進行了比較，并利用3個較大規(guī)模實例與文獻［7］中的GDPSO進行比較。最后，總結(jié)全文并展望下一步的工作。

2 0－1KP問題及其近似算法

背包問題的數(shù)學描述［1，5］為：設(shè)n個物品的價值集為C＝ ｛c1，c2，…，cn｝，重量集為W＝ ｛w1，w2，…，wn｝，ci，wi∈Z＋，1≤i≤n，Z＋為正整數(shù)集；又設(shè)背包載重為M∈Z＋，滿足條件n）。求解向量X＝ （x1，x2，…，xn）∈ ｛0，1｝n，使得

其中，當xi＝1時表示第i個物品裝入背包；當xi＝0時表示第i個物品不裝入背包。一般地，稱背包問題中物品數(shù)n為問題的規(guī)模。

在文獻［8］中，利用貪心策略給出了一種求解0－1KP問題的近似算法，即首先根據(jù)物品的價值重量比由大到小的順序?qū)個物品進行排序，然后從價值重量比大的物品開始依次將物品裝入背包，直到出現(xiàn)某物品的重量超過背包的剩余重量為止，此時所裝入背包中的物品即為0－1KP問題的一個近似解。

若設(shè)n個物品的價值重量比為ci／wi（1≤i≤n），將n個物品按其價值重量比排序。設(shè)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是該解所對應裝入背包物品的價值之和（即近似最優(yōu)值）。GAKP的算法復雜度為O（nlgn），而且已經(jīng)證明其近似比為2［8］。實際上GAKP的貪婪特性還不夠充分，文獻［7］在利用粒子群優(yōu)化算法求解0－1KP問題時注意到這一問題，對貪心策略進一步作了有效改進。下面將利用這種改進的貪心策略，給出一種求解0－1KP問題的改進近似算法。

設(shè)n個物品按其價值重量比排序后的序號依次存放在一維數(shù)組A［1..n］中，即A［1］≥A［2］≥…≥A［n］。又設(shè)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問題的近似最優(yōu)解，S是相應的近似最優(yōu)值。

令XIAKP為IAKP的求得0－1KP問題的近似解，XGAKP為GAKP所求得的近似解。顯然有f（XIAKP）≥f（XGAKP），即XIAKP對應的近似最優(yōu)值優(yōu)于XIAKP的，這是因為當GAKP執(zhí)行第4步時，若條件不滿足則結(jié)束求解；但是對于IAKP，即使w［i］≤Tandi≤n不成立，仍然會繼續(xù)檢查i＋1及其之后的項，從而仍有可能繼續(xù)向背包中裝入物品。因此，IAKP的近似比必然不會超過GAKP，所以IAKP也是2－近似算法。此外，IAKP的復雜度也為O（nlgn）。

3 利用動態(tài)規(guī)劃法求解KP問題

動態(tài)規(guī)劃法（Dynamic programming，DP）是一種求解KP問題的確定性算法，也是一種非常有效的方法，對于規(guī)模不大的0－1KP問題其求解速度相對較快。利用DP求解0－1KP問題時，首先要建立子問題最優(yōu)值之間的遞歸關(guān)系式，然后利用此關(guān)系式由小到大依次求子問題的最優(yōu)值，最終得到的即為原問題的最優(yōu)值，并利用此過程中的信息求得0－1KP問題的最優(yōu)解。

記0－1KP（i，j）是物品數(shù)為i背包載重為j的子問題，令V［i，j］（1≤i≤n，1≤j≤M）表示從物品1，2，…，i中選擇裝入背包載重為j的0－1KP（i，j）子問題的最優(yōu)解，C［1..i］與W［1..i］分別為該子問題中物品的價值集與重量集。又令V［i，0］＝V［0，j］＝0（其中0≤i≤n且0≤j≤M），于是相鄰子問題的最優(yōu)值之間的遞推關(guān)系為：

顯然，0－1KP（n，W）問題即為原始的0－1KP問題，其最優(yōu)值為V［n］［M］。根據(jù)（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被執(zhí)行則說明物品i裝入了背包中，注意到此時V［i］［j］＞V［i－1］［j］，因此利用V［i］［j］的V［i－1］［j］變化容易求得0－1KP問題的最優(yōu)解。于是，在算法3的基礎(chǔ)上，求解0－1KP問題最優(yōu)解與最優(yōu)值的動態(tài)規(guī)劃算法（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(wǎng)［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的輸入規(guī)模，因此算法4實際上是一個偽多項式時間算法。盡管如此，由于它能夠求得0－1KP問題的精確解，因此在實際應用中利用算法4求解規(guī)模不大的0－1KP問題仍然是主要方法之一。

4 仿真計算與比較

下面首先從理論上分析求解0－1KP問題的近似算法IAKP和精確算法DPKP的優(yōu)缺點，然后利用規(guī)模為50，100和200的3個較大規(guī)模的0－1KP實例，通過仿真計算結(jié)果進行驗證，并與文獻［7］中的進化算法GDPSO進行比較。

顯然，近似算法IAKP往往求得0－1KP問題的近似解，而DPKP總是求得問題的精確解。但是，IAKP的時間復雜度為O（nlgn），是多項式時間算法，而DPKP的時間復雜度為O（nM）＝O（n2logM），是一個偽多項式時間算法，即當M的值較大時，耗費的運行時間非常多。因此對于規(guī)模與M均不大的0－1KP實例，利用DPKP求解是首選算法；但對于規(guī)模與M均很大的0－1KP實例，在對解的精度要求不是非常高的情況下，利用IAKP求解是適宜的。

對于0－1KP實例1－3，仿真計算所使用的硬件環(huán)境為DELL Pentium（R）4－CPU1.69GHz微型計算機，128M內(nèi)存；操作系統(tǒng)為Windows XP，并采用VC＋＋6.0進行編程實現(xiàn)。計算結(jié)果見表1，其中給出了各算法所求得的最優(yōu)解（或近似最優(yōu)解）對應的解向量、對應的最優(yōu)值（或近似最優(yōu)值）（用“價值／重量”表示）以及計算各實例所耗費的時間（單位：s）。對于實例1－3，GDPSO的迭代次數(shù)分別為50，100，200，耗費時間為20次計算的平均時間，并取20次計算的最好結(jié)果。GDPSO的其他參數(shù)設(shè)置同文獻［7］中。

實例1［9］規(guī)模為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 規(guī)模為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 規(guī)模為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的計算結(jié)果比較

從表1中可以看出：當?shù)?－1KP實例規(guī)模和背包載重較小時，DPKP能夠耗費較少的時間求得最優(yōu)解，但是隨著問題規(guī)模和背包載重的增大，DPKP所耗費時間的增長幅度非常大，求解速度明顯比IAKP慢。而隨著問題規(guī)模和背包載重的增大，IAKP耗費的時間雖然也逐漸增加，但其增加的趨勢幾乎是線性的，增速非常緩慢；同時，雖然IAKP不一定能夠求得問題的最優(yōu)解，但其求解質(zhì)量與求解速度相對于進化算法GDPOS而言具有明顯的優(yōu)勢。

5 結(jié)束語

本文給出了求解0－1KP問題的改進近似算法IAKP，并與動態(tài)規(guī)劃法DPKP進行了分析和比較，從仿真計算結(jié)果來看，雖然IAKP往往只能求得問題的近似解，但其求解速度遠比DPKP更快，而且通過與進化算法GDPOS的對比還表明IAKP的求解結(jié)果更接近于最優(yōu)解，而且耗費時間也比GDPOS少。所以，對于大規(guī)模且背包載重很大的0－1KP實例，在對解的精度要求不高時，利用IAKP的求解是非常適宜的。今后將進一步研究分枝限界等方法求解0－1KP問題，探討更優(yōu)的求解方法。

［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］ 康立山，謝云，等.非數(shù)值并行算法（一）—模擬退火算法［M］.北京：科學出版社，2003.

［5］ 周明，孫樹棟.遺傳算法原理及其應用［M］.北京：國防工業(yè)出版社，2001.

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

［7］ 劉建芹，賀毅朝，顧茜茜.基于離散微粒群算法求解背包問題研究［J］.計算機工程與設(shè)計，2007，28（13），3189－3191，3204.

［8］ 張德富.算法設(shè)計與分析（高級教程）［M］.北京：國防工業(yè)出版社，2007.

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