劉建芹，王英杰

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

1 引言

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

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

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

背包問題的數(shù)學(xué)描述［1，5］為：設(shè)n個(gè)物品的價(jià)值集為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，使得

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

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

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

設(shè)n個(gè)物品按其價(jià)值重量比排序后的序號(hào)依次存放在一維數(shù)組A［1..n］中，即A［1］≥A［2］≥…≥A［n］。又設(shè)X［1..n］為所求得的解向量，T與S是兩個(gè)臨時(shí)變量，分別存放裝入背包的物品的重量之和與價(jià)值之和，則求解0－1KP問題的改進(jìn)近似算法（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īng)的近似最優(yōu)值。

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

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

動(dòng)態(tài)規(guī)劃法（Dynamic programming，DP）是一種求解KP問題的確定性算法，也是一種非常有效的方法，對(duì)于規(guī)模不大的0－1KP問題其求解速度相對(duì)較快。利用DP求解0－1KP問題時(shí)，首先要建立子問題最優(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］分別為該子問題中物品的價(jià)值集與重量集。又令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）式計(jì)算V［n］［M］的算法（簡(jiǎn)記為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裝入了背包中，注意到此時(shí)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)值的動(dòng)態(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的時(shí)間復(fù)雜度主要取決于步驟2，因此算法4的時(shí)間復(fù)雜度為O（nM）。注意到logM為M的輸入規(guī)模，因此算法4實(shí)際上是一個(gè)偽多項(xiàng)式時(shí)間算法。盡管如此，由于它能夠求得0－1KP問題的精確解，因此在實(shí)際應(yīng)用中利用算法4求解規(guī)模不大的0－1KP問題仍然是主要方法之一。

4 仿真計(jì)算與比較

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

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

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

實(shí)例1［9］規(guī)模為50的0－1KP實(shí)例，其中物品的價(jià)值集為｛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。

實(shí)例2 規(guī)模為100的0－1KP實(shí)例，其中物品的價(jià)值集為｛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。

實(shí)例3 規(guī)模為200的0－1KP實(shí)例，其中物品的價(jià)值集為｛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的計(jì)算結(jié)果比較

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

5 結(jié)束語

本文給出了求解0－1KP問題的改進(jìn)近似算法IAKP，并與動(dòng)態(tài)規(guī)劃法DPKP進(jìn)行了分析和比較，從仿真計(jì)算結(jié)果來看，雖然IAKP往往只能求得問題的近似解，但其求解速度遠(yuǎn)比DPKP更快，而且通過與進(jìn)化算法GDPOS的對(duì)比還表明IAKP的求解結(jié)果更接近于最優(yōu)解，而且耗費(fèi)時(shí)間也比GDPOS少。所以，對(duì)于大規(guī)模且背包載重很大的0－1KP實(shí)例，在對(duì)解的精度要求不高時(shí)，利用IAKP的求解是非常適宜的。今后將進(jìn)一步研究分枝限界等方法求解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］.北京：科學(xué)出版社，2003.

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

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

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

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

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