求解0－1背包問(wèn)題的兩種算法設(shè)計(jì)*

劉朝霞

(集寧師范學(xué)院數(shù)學(xué)系，內(nèi)蒙古 烏蘭察布 012000)

背包問(wèn)題(Knapsack problem)是由Merkel和Hellman在1978年提出的，后來(lái)通過(guò)對(duì)其特點(diǎn)的研究，表明該問(wèn)題是一個(gè)典型的NP－complete問(wèn)題。它被廣泛應(yīng)用在各種工業(yè)場(chǎng)合中，如資本預(yù)算、貨物裝載和存儲(chǔ)分配等問(wèn)題，這些問(wèn)題都可以轉(zhuǎn)化成0－1背包問(wèn)題，因此研究0－1背包問(wèn)題的求解方法具有非常重要的現(xiàn)實(shí)意義［1］。

0－1背包問(wèn)題可描述為:有n個(gè)物品和一個(gè)背包。物品 i的價(jià)值為 vi，重量為 wi(i=1，2，…，n)，背包的容量為jmax。如何在n個(gè)物品中選取若干件裝入背包，使其在背包容量許可下所裝入的物品總價(jià)值最大?本問(wèn)題中，對(duì)于任意第i個(gè)物品只存在裝入背包和不裝入背包兩種選擇，用xi表示對(duì)物品i做出選擇的情況，當(dāng)xi=0時(shí)，表示放棄物品i，即該物品沒(méi)有裝入背包;當(dāng)xi=1時(shí)，表示選擇物品i裝入背包，需要說(shuō)明的是同一物品只能裝入背包一次，也不能只裝入物品的一部分。0－1背包問(wèn)題由此而得名。

1 0－1背包問(wèn)題的數(shù)學(xué)模型

目前，求解0－1背包問(wèn)題主要有精確算法和近似算法兩種方法。精確算法有分支限界法、動(dòng)態(tài)規(guī)劃法等，近似算法有貪心法、群蟻算法、模擬退火算法等［2］。由于0－1背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，滿(mǎn)足貪心算法和動(dòng)態(tài)規(guī)劃算法對(duì)求解問(wèn)題的要求，因此本文就采用動(dòng)態(tài)規(guī)劃法和貪心法求解0－1背包問(wèn)題。

2 求解0－1背包問(wèn)題的算法

2.1 動(dòng)態(tài)規(guī)劃算法(DP)

動(dòng)態(tài)規(guī)劃主要針對(duì)最優(yōu)化問(wèn)題，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。是在20世紀(jì)50年代初，由美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)提出的，動(dòng)態(tài)規(guī)劃算法通常用于求解某種最優(yōu)性質(zhì)的問(wèn)題，分治和解決冗余是其基本思想，將待求解的問(wèn)題分解為規(guī)模大致相同、不相互獨(dú)立的若干子問(wèn)題，然后對(duì)各子問(wèn)題進(jìn)行求解，最終產(chǎn)生一個(gè)整體最優(yōu)解［3］。

2.1.1 動(dòng)態(tài)規(guī)劃法求解0－1背包問(wèn)題的算法設(shè)計(jì)

使用動(dòng)態(tài)規(guī)劃法進(jìn)行算法設(shè)計(jì)，需要推導(dǎo)一個(gè)最優(yōu)值的遞歸關(guān)系式。假設(shè)m［i］［j］是一個(gè)前i－1個(gè)物品已經(jīng)做出選擇的0－1背包子問(wèn)題

的最優(yōu)值，即

因?yàn)橐呀?jīng)對(duì)前i－1個(gè)物品做出了選擇，即序列(x1，x2，...，xi－1)已被確定。在選擇第 i個(gè)物品時(shí)有如下兩種情況之一:

(1)背包剩余容量不足以裝入物品i，即j＜wi時(shí)xi=0，背包的價(jià)值不增加，最大價(jià)值

(2)背包容量能夠裝入物品i，即j≥wi時(shí)，若選擇物品i裝入背包，xi=1，則背包的價(jià)值增加vi，

若選擇物品i不放入背包，xi=0，則m［i］［j］=m［i－ 1］［j］。所以，當(dāng)j≥wi時(shí)，對(duì)有i個(gè)物品的0 － 1背包子問(wèn)題的最優(yōu)解為二者的最大值。由此可得到如下遞推關(guān)系式:

2.1.2 C++語(yǔ)言描述的算法實(shí)現(xiàn)

2.2 貪心法求解0－1背包問(wèn)題

貪心法是一種簡(jiǎn)單、高效的算法設(shè)計(jì)策略，它總是從問(wèn)題的一個(gè)初始解出發(fā)，每一次都根據(jù)貪心策略做出當(dāng)前最優(yōu)的選擇，通過(guò)一次次的局部最優(yōu)解，逐步逼近給定的目標(biāo)，達(dá)到最終的整體最優(yōu)解，這種啟發(fā)式的策略不能對(duì)所有問(wèn)題都獲得最優(yōu)解，但在許多情況下，能得到最優(yōu)解的近似解［4］。因此，在求解NP完全問(wèn)題中該算法具有越來(lái)越重要的作用。

2.2.1 貪心算法設(shè)計(jì)

選擇最優(yōu)的貪心策略是使用貪心法求解0－1背包問(wèn)題時(shí)首先要考慮的問(wèn)題，最優(yōu)的貪心策略能夠使得到的解更接近最優(yōu)解。本問(wèn)題可選擇的貪心策略有三種:

第一種是價(jià)值最大貪心策略:在背包容量許可的情況下選擇價(jià)值最大的物品裝入，直到受到背包容量限制裝不下為止。

第二種是重量最小貪心策略:在背包容量許可的情況下選擇重量最小的物品裝入背包，直到背包裝不下剩余的物品為止。

第三種是價(jià)值重量比貪心策略:在背包容量許可的情況下選擇vi/wi值最大的物品裝入，直到背包裝不下剩余的物品為止。

選擇策略1，如果價(jià)值最大的物品重量太大，這樣背包的容量得不到有效利用。選擇策略2，如果重量小的物品價(jià)值也很低，這樣很難保證背包的價(jià)值最大。策略3，既考慮了價(jià)值又考慮了重量，直觀上，按該種策略可能得到最優(yōu)解。本文就選擇貪心策略3作為最優(yōu)貪心策略來(lái)設(shè)計(jì)0－1背包問(wèn)題的算法。

用貪心策略3求解0－1背包問(wèn)題的步驟如下:求出給定物品的價(jià)值重量比vi/wi(i=1，2，...，n);將物品按照價(jià)值比重的非遞增順序進(jìn)行排序;重復(fù)下面的步驟，直到不滿(mǎn)足條件為止:將價(jià)值重量比最高的物品放入背包，計(jì)算背包的剩余空間，若當(dāng)前背包剩余容量能夠裝入物品則裝入，否則，選擇下一物品。

2.2.2 C++語(yǔ)言描述的算法實(shí)現(xiàn)

3 兩種算法的分析與比較

由以上求解0－1背包問(wèn)題的兩種算法設(shè)計(jì)可知，動(dòng)態(tài)規(guī)劃法和貪心法求解0－1背包問(wèn)題都具有可行性，但這兩種算法又存在一定的其局限性。下面將從時(shí)間和空間復(fù)雜度、準(zhǔn)確性等方面對(duì)這兩種算法進(jìn)行分析。

在運(yùn)用動(dòng)態(tài)規(guī)劃法的算法實(shí)現(xiàn)KnapSack函數(shù)中，由于算法的基本語(yǔ)句是衡量算法運(yùn)行時(shí)間的主要依據(jù)，為此，選定if(w［i］＜=j)作為基本語(yǔ)句，該語(yǔ)句之執(zhí)行的次數(shù)n×jmax，所以，該算法的時(shí)間復(fù)雜性為O(n×jmax)。由此可見(jiàn)，當(dāng)背包容量jmax較大、問(wèn)題規(guī)模n較大時(shí)，算法需要的計(jì)算時(shí)間較多，例如，當(dāng)jmax＞2n時(shí)，算法需要O(n×2n)的計(jì)算時(shí)間。所以，動(dòng)態(tài)規(guī)劃法適合于規(guī)模較小問(wèn)題的求解，但能保證求解的正確性。

貪心算法的主要計(jì)算時(shí)間將耗費(fèi)在對(duì)物品按照價(jià)值比重進(jìn)行非遞增排序上，由于本文使用快速排序來(lái)實(shí)現(xiàn)價(jià)值比重的排序，因此算法的時(shí)間復(fù)雜度為O(nlogn)。然而，貪心算法屬于近似算法，雖然速度快，但不一定是最優(yōu)解。如對(duì)于n=3，jmax=50，wi=(10，20，30)，vi=(60，100，120)，其中i=1，2，3的0－1背包問(wèn)題，按照貪心策略3做選擇，由于物品1的價(jià)值比重最大，應(yīng)首選物品1裝入背包，但事實(shí)上選擇第二個(gè)物品才是本問(wèn)題的最優(yōu)解，體現(xiàn)了該算法的局限性。

4 結(jié)束語(yǔ)

求解0－1背包問(wèn)題除了精確算法－動(dòng)態(tài)規(guī)劃法和近似算法－貪心法外，還可以用回溯法、分支限界法、蟻群算法、DNA算法、粒子群優(yōu)化算法等算法。但由于0－1背包問(wèn)題是一個(gè)NP問(wèn)題，對(duì)于規(guī)模較大的0－1背包問(wèn)題還沒(méi)有找到一種最佳的求解方法，也就是說(shuō)，現(xiàn)有的每一種智能算法都有不同程度的局限性，都是在一定范圍內(nèi)求解。因此，這就需要我們?cè)谠兴惴ǖ睦碚摶A(chǔ)上進(jìn)一步研究，不斷地改進(jìn)和優(yōu)化算法，最終能找到求解0－1背包問(wèn)題的最佳方法。

［1］王曉東.算法設(shè)計(jì)與分析(第二版)［M］.北京:清華大學(xué)出版社，2008.

［2］王秋芬，呂聰穎，周春光.算法設(shè)計(jì)與分析［M］.北京:清華大學(xué)出版社，2011.

［3］李北斗.關(guān)于0－1背包問(wèn)題的算法研究［J］.計(jì)算機(jī)與數(shù)字工程，2008，(5).

［4］田烽楠，王于.求解0－1背包問(wèn)題算法綜述［J］.軟件導(dǎo)刊，2009，(1).