背包問題的多種解法

1、nnn問題描述0/1 背包問題 :現(xiàn)有n種物品，對1<=i<=n ，已知第i種物品的重量為正整數(shù) Wi，價值為正整數(shù) Vi, 背包能承受的最大載重量為正整數(shù)W，現(xiàn)要求找出這n種物品的一個子集，使得子集中物品的總重量不超過 W 且總價值盡量大。 (注意：這里對每種物品或者全取或者一點都不取， 不允許只取一部分)算法分析根據(jù)問題描述，可以將其轉(zhuǎn)化為如下的約束條件和目標(biāo)函數(shù)：n wi xi Wi 1 i i (1)xi 0,1( 1 i n)nmaxvi xi (2)i1于是，問題就歸結(jié)為尋找一個滿足約束條件( 1 )，并使目標(biāo)函數(shù)式( 2 )達(dá)到最大的解向量 X(x1, x2 ,x3,

2、 xn) 。首先說明一下 0-1 背包問題擁有最優(yōu)解。假設(shè)(Xi,X2,X3,，Xn)是所給的問題的一個最優(yōu)解， 則(X2,X3,，Xn)是下面問題的一個最優(yōu)解：wiXiWi2w1X1nmaX vi Xi 。如果不是的話，設(shè)(y2,y3, yn) 是這Xi 0,1( 2i n)i2nnn個問 題的 一 個 最 優(yōu)解 ， 則viyiviXi ， 且 w1X1wiyi W 。因 此 ，i 2i 2i 2V1X1Viyi V1X1ViViXi，這說明(Xi,y2,y3,yn)是所給的 0-1 背包問i 2i 2i 1題比(Xi,X2,X3, Xn)更優(yōu)的解，從而與假設(shè)矛盾。窮舉法：用窮舉法解決0-1

3、背包問題，需要考慮給定 n個物品集合的所有子集，找出所有可能的子集(總重量不超過背包重量的子集)，計算每個子集的總重量，然后在他們中找到價值最大的子集。由于程序過于簡單，在這里就不再給出，用實例說明求解過程。下面給出了 4個物品和一個容量為 10的背包，下圖就是用窮舉法求解0-1背包問題的過程。背包W1=7V1=12物品1W2=3V2=12物品2W3=4V3=40物品3W4=5V4=25物品4(a) 四個物品和一個容量為10的背包序號子集總重量總價值序號子集總重量總價值1空集0092，375221742102，483732312113，496543440121,2,314不可行54525131

4、,2,415不可行61，21054141,3,416不可行71，311不可行152,3,412不可行81 ,412不可行16123,419不可行(b)用回溯法求解 0-1背包問題的過程遞歸法：在利用遞歸法解決 0-1背包問題時，我們可以先從第n個物品看起。每次的遞歸調(diào)用都會判斷兩種情況：(1) 背包可以放下第 n個物品，則xn=1 ，并繼續(xù)遞歸調(diào)用物品重量為W-wn,物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值與 vn的和作為背包問題的 最優(yōu)解；(2) 背包放不下第n個物品，則xn=0，并繼續(xù)遞歸調(diào)用背包容量為W，物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值最為背包問題的最優(yōu)解。遞歸調(diào)用的

5、終結(jié)條件是背包的容量為0或物品的數(shù)量為0.此時就得到了 0-1背包問題的最優(yōu)解。用遞歸法解0-1背包問題可以歸結(jié)為下函數(shù)：KnapSack(n 1,m)沒有選擇物品nKnapSack(n,m)一"KnapSack(n 1,m wn) vn選擇了物品 n第一個式子表示選擇物品n后得到價值KnapSack(n 1, m wn) vn比不選擇物品n情況下得到的價值 KnapSack(n 1, m)小，所以最終還是不選擇物品n;第二個式子剛好相反，選擇物品n后的價值KnapSack(n 1,m wn) vn不小于不選擇物品 n 情況下得到了價值 KnapSack( n 1, m)，所以最終選

6、擇物品n。在遞歸調(diào)用的過程中可以順便求出所選擇的物品。下面是標(biāo)記物品被選情況的數(shù)組xn求解的具體函數(shù)表示：0KnapSack (n,m) KnapSack(n 1,m)xn1KnapSack (n,m) KnapSack (n 1,m wn) vn在函數(shù)中，遞歸調(diào)用的主體函數(shù)為KnapSack ， m 表示背包的容量， n 表示物品的數(shù)量，xn表示是否選擇了第 n個物品(1 選，0 不選)。每個物品的重量和價值信息分 別存放在數(shù)組 wn 和 vn 中。具體的代碼見遞歸法文件夾。貪心法：0-1背包問題與背包問題類似，所不同的是在選擇物品i(1 i n)裝入背包時，可以選擇一部分，而不一定要全部裝

7、入背包。 這兩類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，相當(dāng)相似。但 是背包問題可以用貪心法求解，而 0-1 背包問題卻不能用貪心法求解。貪心法之所以得不 到最優(yōu)解， 是由于物品不允許分割， 因此，無法保證最終能將背包裝滿，部分閑置的背包容 量使背包單位重量的價值降低了。事實上，在考慮 0-1 背包問題時，應(yīng)比較選擇物品和不選擇物品所導(dǎo)致的方案，然后做出最優(yōu)解。由此導(dǎo)出了許多相互重疊的子問題，所以，0-1背包問題可以用動態(tài)規(guī)劃法得到最優(yōu)解。在這里就不再用貪心法解0-1 背包問題了。動態(tài)規(guī)劃法分析：0-1 背包問題可以看作是尋找一個序列 ( x1, x2, x3 , , xn ) ，對任一個變量 xi 的判斷

8、是決定 xi =1 還是 xi =0. 在判斷完 xi 1 之后，已經(jīng)確定了 ( x1, x2, x3 , , xi 1) ，在判斷 xi時，會有兩種情況：(1) 背包容量不足以裝入物品i，則Xj =0，背包的價值不增加；(2) 背包的容量可以裝下物品i，則Xj=1，背包的價值增加Vj。這兩種情況下背包的總價值的最大者應(yīng)該是對Xj判斷后的價值。令 C(i, j)表示在前i(1 i n)個物品中能夠裝入容量為 j(1 j W)的背包的物品的總價值，則可以得到如下的動態(tài)規(guī)劃函數(shù)：C(i,0) C(0, j) 0(1)C(i 1, j)j wiC(i, j )i(2)maXC(i 1, j),C(i

9、 1, j wi) vi j wi式(1)說明：把前面i個物品裝入容量為 0的背包和把0個物品裝入容量為j的背包, 得到的價值均為 0.式(2)第一個式子說明：如果第 i 個物品的重量大于背包的容量，則裝 入第 i 個物品得到的最大價值和裝入第 i-1 個物品得到的最大價值是相同的， 即物品 i 不能 裝入背包中；第二個式子說明：如果第 i 個物品的重量小于背包的容量，則會有兩種情況： ( 1 )如果把第 i 個物品裝入背包，則背包中物品的價值就等于把前 i-1 個物品裝入容量為j Wi的背包中的價值加上第i個物品的價值v ; (2 )如果第i個物品沒有裝入背包，貝y背 包中物品的價值就是等于

10、把前 i-1 個物品裝入容量為 j 的背包中所取得的價值。 顯然，取二 者中價值較大者作為把前 i個物品裝入容量為j的背包中的最優(yōu)解。我們可以一步一步的解出我們所需要的解。第一步，只裝入第一個物品，確定在各種情況下背包能得到的最大價值；第二步，只裝入前兩個物品，確定在各種情況下的背包能 夠得到的最大價值； 一次類推， 到了第 n 步就得到我們所需要的最優(yōu)解了。 最后， C(n,W) 便是在容量為 W 的背包中裝入 n 個物品時取得的最大價值。為了確定裝入背包的具體物 品，從C(n,W)的值向前尋找，如果C(n,W)>C(n 1,W),說明第n個物品被裝入了背包 中，前n-1個物品被裝入容

11、量為 W wn的背包中；否則，第 n個物品沒有裝入背包中，前 n-1 個物品被裝入容量為 W 的背包中。依此類推，直到確定第一個物品是否被裝入背包為止。由此，我們可以得到如下的函數(shù)：0C(i, j) C(i 1, j)1, j j wiC(i, j) C(i 1,j)根據(jù)動態(tài)規(guī)劃函數(shù)，用一個(n 1) (W 1)的二維數(shù)組C存放中間變量，Cij表示把前 i 個物品裝入容量為 j 的背包中獲得的最大價值。設(shè)物品的重量存放在數(shù)組wn中，價值存放在數(shù)組 vn中，背包的容量為 W，數(shù)組Cn 1W1存放迭代的結(jié)果，數(shù)組 xn 存放裝入背包的物品，動態(tài)規(guī)劃解 0-1 背包問題的源代碼在文件夾動態(tài)規(guī)劃法中。

12、回溯法分析：用回溯法解 0_1 背包問題時， 會用到狀態(tài)空間樹。 在搜索狀態(tài)空間樹時， 只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進(jìn)入其左子樹。當(dāng)右子樹有可能包含最優(yōu)解時才進(jìn)入右子樹搜索，否則將右子樹剪去。設(shè) r 是當(dāng)前剩余物品價值總和； cp 是當(dāng)前價值； bestp 是當(dāng)前 最優(yōu)價值。當(dāng)cp+r E)estp時，可剪去右子樹。計算右子樹中解的上界可以用的方法是將 剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一 部分而裝滿背包。由此得到的價值是右子樹中解的上界，用此值來剪枝。為了便于計算上界， 可先將物品依其單位重量價值從大到小排序， 此后只要順序考察各 物品即可

13、。在實現(xiàn)時，由 MaxBoundary 函數(shù)計算當(dāng)前結(jié)點處的上界。它是類 Knap 的私 有成員。 Knap 的其他成員記錄了解空間樹種的節(jié)點信息，以減少函數(shù)參數(shù)的傳遞以及遞 歸調(diào)用時所需要的?？臻g。在解空間樹的當(dāng)前擴(kuò)展結(jié)點處，僅當(dāng)要進(jìn)入右子樹時才計算上 界函數(shù) MaxBoundary ，以判斷是否可以將右子樹減去。進(jìn)入左子樹時不需要計算上界， 因為其上界與父結(jié)點的上界相同。在調(diào)用函數(shù) Knapsack 之前， 需要先將各物品依其單位重量價值從達(dá)到小排序。 為此目 的，我們定義了類 Objiect 。其中， 運算符與通常的定義相反，其目的是為了方便調(diào)用 已有的排序算法。在通常情況下，排序算法將

14、待排序元素從小到大排序。在搜索狀態(tài)空間樹時， 由函數(shù) Backtrack 控制。 在函數(shù)中是利用遞歸調(diào)用的方法實現(xiàn)了 空間樹的搜索。具體的代碼見回溯法文件夾。限界分支法：在解 0-1 背包問題的優(yōu)先隊列式界限分支法中，活結(jié)點優(yōu)先隊列中結(jié)點元素N 的優(yōu)先級由該結(jié)點的上界函數(shù) MaxBoundary 計算出的值 uprofit 給出。該上界函數(shù)在 0-1 背包 問題的回溯法總已經(jīng)說明過了。 子集樹中以結(jié)點 N 為根的子樹中任一個結(jié)點的價值不超過 N.profit 。因此我們用一個最大堆來實現(xiàn)活結(jié)點優(yōu)先隊列。堆中元素類型為HeapNode,其私有成員有 uprofit,profit,weight,l

15、evel, 和 ptr 。對于任意一個活結(jié)點 N ， N.weight 是 活結(jié)點 N 所相應(yīng)的重量； N.profit 是 N 所相應(yīng)的價值； N.uprofit 是結(jié)點 N 的價值上界， 最大堆以這個值作為優(yōu)先級。子集空間樹中結(jié)點類型為 bbnode 。在分支限界法中用到的類 Knap 與 0-1 背包問題的回溯法中用到的類 Knap 很相似。 他們的區(qū)別是新的類中沒有了成員變量 bestp ，而增加了新的成員 bestx 。 Bestxi=1, 當(dāng) 且僅當(dāng)最優(yōu)解含有物品 i。在類 Knap 中有四個函數(shù)：(1 ) 上界函數(shù) MaxBoundary(), 計算節(jié)點所對應(yīng)價值的上界；(2 )

16、 函數(shù) AddLiveNode() 是將一個新的活結(jié)點插入到子集樹和優(yōu)先隊列中；(3 ) 函數(shù) MaxKnapsack() 實施對子集樹的優(yōu)先隊列式分支界限搜索。其中假定物 品依其單位價值從大到小已經(jīng)排好序。 相應(yīng)的排序過程會在算法的預(yù)處理部分 完成。算法中 E 是當(dāng)前擴(kuò)展結(jié)點； cw 是該結(jié)點的重量； cp 是該結(jié)點的價值； up 是價值上界。算法的 while 循環(huán)不斷擴(kuò)展結(jié)點，直到子集樹的一個葉結(jié)點 成為擴(kuò)展結(jié)點為止。 此時優(yōu)先隊列中所有活結(jié)點的價值上界均不超過該葉結(jié)點 的價值。因此該葉結(jié)點相應(yīng)的解為問題的最優(yōu)解。在 while 循環(huán)內(nèi)部，算法首先檢查當(dāng)前擴(kuò)展結(jié)點的左兒子結(jié)點的可行性。如

17、果 該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當(dāng)前擴(kuò) 展結(jié)點的右兒子結(jié)點一定是可行結(jié)點， 僅當(dāng)右兒子結(jié)點滿足上界約束時才將它 加入子集樹和活結(jié)點優(yōu)先隊列。(4 ) 函數(shù) Knapsack() 完成對輸入數(shù)據(jù)的處理。其主要任務(wù)是將各物品依其單位重 量價值從達(dá)到小排好序。然后調(diào)用函數(shù) MaxKnapsack() 完成對子集樹的優(yōu)先 隊列式分支限界搜索。具體的實現(xiàn)代碼在文件夾分支限界法中。三、 時 空效率分析窮舉法：對于一個有 n 個元素的集合，其子集數(shù)量為 2n ，所以，不論生成子集的算法效率有 多高，窮舉法都會導(dǎo)致一個 O(2n) 的算法。遞歸法：在遞歸法的算法體中有一個 i

18、f 判斷中出現(xiàn)了兩次遞歸調(diào)用比較大小所以它們之間的遞歸關(guān)系式可以大體表示為： T(n) 2T(n 1) C，其中T(n)表示遞歸法的時間復(fù)雜度， C是常數(shù)。求解遞歸方程可以知道 T(n)的量級為o(2n)。所以遞歸法解0-1背包問題的 時間復(fù)雜度為O(2n)。遞歸法是耗費空間最多的算法，每次遞歸調(diào)用都需要壓棧，導(dǎo)致 棧的使用很頻繁。動態(tài)規(guī)劃法：由于函數(shù) Knapsack 中有一個兩重 for 循環(huán)，所以時間復(fù)雜度為 O(n+1)x(m+1). 空間復(fù)復(fù)雜度也是 O(n+1)x(m+1) ，即 O(nm ).回溯法：由于計算上界的函數(shù) MaxBoundary 需要O(n)時間，在最壞情況下有 O

19、(2n)個右兒 子結(jié)點需要計算上界，所以解 0-1 背包問題的回溯法算法 BackTrack 所需要的計算時 間為 O(n2n).限界分支法：在使用限界分治法時， 就是使用更好的限界剪枝函數(shù)使得不必要的解被剔除，但是在最壞情況下的解仍然是和回溯法是相同的。本算法中也是用到了計算上界的函數(shù)MaxBoundary 需要O(n)的時間，而且在最壞情況下有 O(2n)個結(jié)點需要計算上界，所以在最壞情況下的時間復(fù)雜度仍然為 O(n2n) 。四、運行結(jié)果遞歸法輸出結(jié)果:題遞歸法J曲容重Z和物詁個牧W :C;u KXAdnni n SstrartorKDekto fA 算法恨IE痕飯呃 502 00王母 0

20、.1 苜包口弧 譴歸曲Knaw®xwe£0 10植輸入每個物呂的重量缶）和物品的價值3）：H 3412 3224昭16 67b b49 3S3 4G21 56IS4£19 ?9背包的最優(yōu)辭為：225最優(yōu)解條禪下選擇的脊剋為二孟容臺*節(jié)和物器個數(shù)（町=動態(tài)規(guī)劃法輸出結(jié)果:4b006Bi3466和價值32 3b的容量()和物詁個數(shù)葉丄肯10軒次輸入每個物品的重量(- 0 34 12 竝 24 Sb lb 67 b !>£ 胃赳的最優(yōu)解為：P2&杲憂解條件T的囲罩的背包九1&a1莊此過程中用刮的Bn “ 1數(shù)組數(shù)據(jù)為 0U甘回溯法輸出結(jié)果

21、:p"肯包何題一一回砸i 淸輔入皆R容量5： 植輸入物品曲個教<“>：楕輸人切1界價喈<»>:34 32 盹 t7 &4 32 45 血 7& 請捕入物品的重#<«> =姑 1H 昭 “ £ 乎 35» 21 18 1?K藝g"值為 <l>B8tp> Sf/oC:UsersAdm n istrator De? kto pfEit1»20030502 DO J3 王母0.1 苜包口亞叵滯熱B氛分枝限界法輸出結(jié)果:I C ;U sersXAdrrn n i5t

22、ratorDe?ktc pj£fEJlE1SZC030602 00王母口丄苜包冃左袁股齊洼“ I 1=1 丨同背包何題一一分核限網(wǎng)i腎輛入皆包曲容量（c）糸威品個數(shù) M : 18 ?障一欽輸入每個物品的重量G）和價值 4 Li ?* $4 9B 12V 136 4LG 14背包的最優(yōu)解為：3Q最優(yōu)解條樣丁的雋擇的背旦為311000請輸入背包的容量（C）和物品個數(shù)（町，Gp占4G21 56ie 46p ?0賛包的最優(yōu)解知幕優(yōu)解條伴卜的詵擇茁肖刖為1301請輔人背包的春量（c）和物品小數(shù)怛幕幫繇f枝限異迭 討10 陌一次輸入每個物胡的重量H 3412 3204 （6U t7k b4容量任）和物品個數(shù)（町 和價值五、分析輸出結(jié)果上面測試的是每種算法在兩種輸入情況下得到的0-1背包問題的解。兩種測試數(shù)據(jù)為:第一組：背包容量：18 ;物品數(shù)目:7;每個物品重量為：11 2489610 ；每個物