背包問(wèn)題的多種解法

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

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

3、背包問(wèn)題，需要考慮給定 n個(gè)物品集合的所有子集，找出所有可能的子集(總重量不超過(guò)背包重量的子集)，計(jì)算每個(gè)子集的總重量，然后在他們中找到價(jià)值最大的子集。由于程序過(guò)于簡(jiǎn)單，在這里就不再給出，用實(shí)例說(shuō)明求解過(guò)程。下面給出了 4個(gè)物品和一個(gè)容量為 10的背包，下圖就是用窮舉法求解0-1背包問(wèn)題的過(guò)程。背包W1=7V1=12物品1W2=3V2=12物品2W3=4V3=40物品3W4=5V4=25物品4(a) 四個(gè)物品和一個(gè)容量為10的背包序號(hào)子集總重量總價(jià)值序號(hào)子集總重量總價(jià)值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背包問(wèn)題的過(guò)程遞歸法：在利用遞歸法解決 0-1背包問(wèn)題時(shí)，我們可以先從第n個(gè)物品看起。每次的遞歸調(diào)用都會(huì)判斷兩種情況：(1) 背包可以放下第 n個(gè)物品，則xn=1 ，并繼續(xù)遞歸調(diào)用物品重量為W-wn,物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值與 vn的和作為背包問(wèn)題的 最優(yōu)解；(2) 背包放不下第n個(gè)物品，則xn=0，并繼續(xù)遞歸調(diào)用背包容量為W，物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值最為背包問(wèn)題的最優(yōu)解。遞歸調(diào)用的

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

6、擇物品n。在遞歸調(diào)用的過(guò)程中可以順便求出所選擇的物品。下面是標(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個(gè)物品(1 選，0 不選)。每個(gè)物品的重量和價(jià)值信息分 別存放在數(shù)組 wn 和 vn 中。具體的代碼見(jiàn)遞歸法文件夾。貪心法：0-1背包問(wèn)題與背包問(wèn)題類似，所不同的是在選擇物品i(1 i n)裝入背包時(shí)，可以選擇一部分，而不一定要全部裝

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

8、是決定 xi =1 還是 xi =0. 在判斷完 xi 1 之后，已經(jīng)確定了 ( x1, x2, x3 , , xi 1) ，在判斷 xi時(shí)，會(huì)有兩種情況：(1) 背包容量不足以裝入物品i，則Xj =0，背包的價(jià)值不增加；(2) 背包的容量可以裝下物品i，則Xj=1，背包的價(jià)值增加Vj。這兩種情況下背包的總價(jià)值的最大者應(yīng)該是對(duì)Xj判斷后的價(jià)值。令 C(i, j)表示在前i(1 i n)個(gè)物品中能夠裝入容量為 j(1 j W)的背包的物品的總價(jià)值，則可以得到如下的動(dòng)態(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)說(shuō)明：把前面i個(gè)物品裝入容量為 0的背包和把0個(gè)物品裝入容量為j的背包, 得到的價(jià)值均為 0.式(2)第一個(gè)式子說(shuō)明：如果第 i 個(gè)物品的重量大于背包的容量，則裝 入第 i 個(gè)物品得到的最大價(jià)值和裝入第 i-1 個(gè)物品得到的最大價(jià)值是相同的， 即物品 i 不能 裝入背包中；第二個(gè)式子說(shuō)明：如果第 i 個(gè)物品的重量小于背包的容量，則會(huì)有兩種情況： ( 1 )如果把第 i 個(gè)物品裝入背包，則背包中物品的價(jià)值就等于把前 i-1 個(gè)物品裝入容量為j Wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值v ; (2 )如果第i個(gè)物品沒(méi)有裝入背包，貝y背 包中物品的價(jià)值就是等于

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

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

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

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

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

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

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

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

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

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

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

21、:p"肯包何題一一回砸i 淸輔入皆R容量5： 植輸入物品曲個(gè)教<“>：楕輸人切1界價(jià)喈<»>:34 32 盹 t7 &4 32 45 血 7& 請(qǐng)捕入物品的重#<«> =姑 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）糸威品個(gè)數(shù) M : 18 ?障一欽輸入每個(gè)物品的重量G）和價(jià)值 4 Li ?* $4 9B 12V 136 4LG 14背包的最優(yōu)解為：3Q最優(yōu)解條樣丁的雋擇的背旦為311000請(qǐng)輸入背包的容量（C）和物品個(gè)數(shù)（町，Gp占4G21 56ie 46p ?0賛包的最優(yōu)解知幕優(yōu)解條伴卜的詵擇茁肖刖為1301請(qǐng)輔人背包的春量（c）和物品小數(shù)怛幕幫繇f枝限異迭 討10 陌一次輸入每個(gè)物胡的重量H 3412 3204 （6U t7k b4容量任）和物品個(gè)數(shù)（町 和價(jià)值五、分析輸出結(jié)果上面測(cè)試的是每種算法在兩種輸入情況下得到的0-1背包問(wèn)題的解。兩種測(cè)試數(shù)據(jù)為:第一組：背包容量：18 ;物品數(shù)目:7;每個(gè)物品重量為：11 2489610 ；每個(gè)物