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

1、 問(wèn)題描述 0/1 背包問(wèn)題 : 現(xiàn)有 n 種物品，對(duì) 1=iC(n 1,W ) ,說(shuō)明第 n個(gè)物品被裝入了背包 中，前 n-1 個(gè)物品被裝入容量為 W wn的背包中；否則，第 n 個(gè)物品沒(méi)有裝入背包中， 前 n-1 個(gè)物品被裝入容量為 W 的背包中。依此類(lèi)推，直到確定第一個(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存放中間變量， Ci j表 示把前 i個(gè)物品裝入容量為 j 的背包中獲得的最大價(jià)值。 設(shè)物品的重量存放在數(shù)組 wn

2、 中，價(jià)值存放在數(shù)組 vn 中，背包的容量為 W ，數(shù)組 Cn 1W 1存放迭代的結(jié)果，數(shù)組 xn 存放裝入背包的物品，動(dòng)態(tài)規(guī)劃解 0-1 背包問(wèn) 題的源代碼在文件夾動(dòng)態(tài)規(guī)劃法中。 回溯法分析： 用回溯法解 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 bestp 時(shí)，可剪去右子樹(shù)。計(jì)算右子樹(shù)中解的上界可以用的方法是將 剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物

3、品，直至裝不下時(shí)，再裝入該物品的一 部分而裝滿背包。由此得到的價(jià)值是右子樹(shù)中解的上界，用此值來(lái)剪枝。 為了便于計(jì)算上界， 可先將物品依其單位重量?jī)r(jià)值從大到小排序， 此后只要順序考察各 物品即可。在實(shí)現(xiàn)時(shí)，由 MaxBoundary 函數(shù)計(jì)算當(dāng)前結(jié)點(diǎn)處的上界。它是類(lèi) Knap 的私 有成員。 Knap 的其他成員記錄了解空間樹(shù)種的節(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞 歸調(diào)用時(shí)所需要的棧空間。在解空間樹(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

4、 之前， 需要先將各物品依其單位重量?jī)r(jià)值從達(dá)到小排序。 為此目 的，我們定義了類(lèi) Objiect 。其中， 運(yùn)算符與通常的定義相反，其目的是為了方便調(diào)用 已有的排序算法。在通常情況下，排序算法將待排序元素從小到大排序。 在搜索狀態(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ù)

5、中以結(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ì)列。堆中元素類(lèi)型為 HeapNode, 其私有成員有 uprofit,profit,weight,level, 和 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)類(lèi)型為 bbnode 。 在分支限界法中用到的類(lèi) Knap 與 0-1 背包問(wèn)題的回溯法中用到的類(lèi) Knap 很相似。 他們的區(qū)別是新的類(lèi)中沒(méi)有了成員變量 b

6、estp ，而增加了新的成員 bestx 。 Bestxi=1, 當(dāng) 且僅當(dāng)最優(yōu)解含有物品 i。 在類(lèi) Knap 中有四個(gè)函數(shù)： (1 ) 上界函數(shù) MaxBoundary(), 計(jì)算節(jié)點(diǎn)所對(duì)應(yīng)價(jià)值的上界； (2 ) 函數(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é)

7、點(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)的可行性。如果 該左兒子結(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ì)列式分支限界搜索。 具體的

8、實(shí)現(xiàn)代碼在文件夾分支限界法中。 三、 時(shí) 空效率分析 窮舉法： 對(duì)于一個(gè)有 n 個(gè)元素的集合，其子集數(shù)量為 2n ，所以，不論生成子集的算法效率有 多高，窮舉法都會(huì)導(dǎo)致一個(gè) O(2n) 的算法。 遞歸法： 在遞歸法的算法體中有一個(gè) if 判斷中出現(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ī)劃

9、法： 由于函數(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(2n ) 個(gè)右兒 子結(jié)點(diǎn)需要計(jì)算上界，所以解 0-1 背包問(wèn)題的回溯法算法 BackTrack 所需要的計(jì)算時(shí) 間為 O(n2n) . 限界分支法： 在使用限界分治法時(shí)， 就是使用更好的限界剪枝函數(shù)使得不必要的解被剔除， 但是在 最壞情況下的解仍然是和回溯法是相同的。本算法中也是用到了計(jì)算上界的函數(shù) MaxBoundary 需

10、要 O(n) 的時(shí)間，而且在最壞情況下有 O(2n) 個(gè)結(jié)點(diǎn)需要計(jì)算上界，所 以在最壞情況下的時(shí)間復(fù)雜度仍然為 O(n2n) 。 四、 運(yùn) 行結(jié)果 遞歸法輸出結(jié)果： 動(dòng)態(tài)規(guī)劃法輸出結(jié)果： 回溯法輸出結(jié)果： 分枝限界法輸出結(jié)果： 五、 分 析輸出結(jié)果 面測(cè)試的是每種算法在兩種輸入情況下得到的 0-1 背包問(wèn)題的解。兩種測(cè)試數(shù)據(jù)為： 第一組：背包容量： 18 ； 物品數(shù)目 ： 7 ； 每個(gè)物品重量為： 11 2 4 8 9 6 10； 每個(gè)物品價(jià)值為： 7 8 8 12 13 4 14 。 第二組：背包容量： 50 ； 物品數(shù)目 ： 10 ； 每個(gè)物品重量為： 8 12 24 16 6 9 35

11、21 18 19 ； 每個(gè)物品價(jià)值為： 34 32 56 67 54 32 45 56 46 70 。 但是可能是算法設(shè)計(jì)時(shí)的問(wèn) 四種實(shí)現(xiàn)的算法中， 只有回溯法沒(méi)能夠得到預(yù)期的最優(yōu)解。 題，其實(shí)回溯法是窮舉法的變形，肯定能夠得到最優(yōu)解的，這里是我設(shè)計(jì)函數(shù)的問(wèn)題。 從遞 歸法的輸出可知， 它的結(jié)果就是我們想要的最優(yōu)解） 。從時(shí)間復(fù)雜度和空間復(fù)雜度分析可知， 動(dòng)態(tài)規(guī)劃法的時(shí)間復(fù)雜度是最小的， 但是同時(shí)它的空間復(fù)雜度又是最大的。 這里就可以看出 在設(shè)計(jì)算法的過(guò)程中要考慮它們的平衡問(wèn)題。 在時(shí)間要求比較快的情況下， 我們就可以選擇 動(dòng)態(tài)規(guī)劃法； 在空間要求比較高時(shí)， 我們就可以使用窮舉法或是分枝限界法等其他改進(jìn)的窮 舉法。 各種算法在解背包問(wèn)題時(shí)的比較如下表所示： 算法名稱 時(shí)間復(fù)雜度 優(yōu)點(diǎn) 缺點(diǎn) 改進(jìn) 窮舉法 O(2n) 最優(yōu)解 速度慢 剪枝 遞歸法 O(2n) 最優(yōu)解 空間消耗大 用數(shù)組存 動(dòng)態(tài)規(guī)劃法 O(nm) 最優(yōu)解 速度慢 遞歸方程求解 貪心法 O(nlog 2 n) 不一定是最優(yōu)解 速度快 可以作為啟發(fā) 回溯法 O(n2n) 最優(yōu)解 速度慢 改進(jìn)剪枝 分枝限界法 O(n2n) 最優(yōu)解 速度慢 優(yōu)化限界函數(shù) 從計(jì)算復(fù)雜性理論看， 背包問(wèn)題是 NP 完全問(wèn)題。 半個(gè)多世紀(jì)以來(lái)， 該問(wèn)題一直是算法 與復(fù)雜性研究的熱門(mén)話題。通過(guò)對(duì) 0-