算法分析與設(shè)計實驗報告之01背包問題

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)專心---專注---專業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專心---專注---專業(yè)算法分析與設(shè)計實驗報告[0/1背包問題]0/1背包問題的不同算法解決方案組員黃希龍張育強周麒

目錄一.問題描述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ù)：于是，問題就歸結(jié)為尋找一個滿足約束條件（1），并使目標(biāo)函數(shù)式（2）達(dá)到最大的解向量。首先說明一下0-1背包問題擁有最優(yōu)解。假設(shè)是所給的問題的一個最優(yōu)解，則是下面問題的一個最優(yōu)解：。如果不是的話，設(shè)是這個問題的一個最優(yōu)解，則，且。因此，，這說明是所給的0-1背包問題比更優(yōu)的解，從而與假設(shè)矛盾。1.窮舉法：用窮舉法解決0-1背包問題，需要考慮給定n個物品集合的所有子集，找出所有可能的子集（總重量不超過背包重量的子集），計算每個子集的總重量，然后在他們中找到價值最大的子集。由于程序過于簡單，在這里就不再給出，用實例說明求解過程。下面給出了4個物品和一個容量為10的背包，下圖就是用窮舉法求解0-1背包問題的過程。四個物品和一個容量為10的背包序號子集總重量總價值序號子集總重量總價值1空集009{2，3}7522{1}74210{2，4}8373{2}31211{3，4}9654{3}44012{1,2,3}14不可行5{4}52513{1,2,4}15不可行6{1，2}105414{1,3,4}16不可行7{1，3}11不可行15{2,3,4}12不可行8{1，4}12不可行16{1,2,3,4}19不可行窮舉法代碼如下:2.遞歸法：在利用遞歸法解決0-1背包問題時，我們可以先從第n個物品看起。每次的遞歸調(diào)用都會判斷兩種情況：背包可以放下第n個物品，則x[n]=1，并繼續(xù)遞歸調(diào)用物品重量為W-w[n],物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值與v[n]的和作為背包問題的最優(yōu)解；背包放不下第n個物品，則x[n]=0，并繼續(xù)遞歸調(diào)用背包容量為W，物品數(shù)目為n-1的遞歸函數(shù)，并返回此遞歸函數(shù)值最為背包問題的最優(yōu)解。遞歸調(diào)用的終結(jié)條件是背包的容量為0或物品的數(shù)量為0.此時就得到了0-1背包問題的最優(yōu)解。用遞歸法解0-1背包問題可以歸結(jié)為下函數(shù)：第一個式子表示選擇物品n后得到價值比不選擇物品n情況下得到的價值小，所以最終還是不選擇物品n;第二個式子剛好相反，選擇物品n后的價值不小于不選擇物品n情況下得到了價值，所以最終選擇物品n。在遞歸調(diào)用的過程中可以順便求出所選擇的物品。下面是標(biāo)記物品被選情況的數(shù)組x[n]求解的具體函數(shù)表示：在函數(shù)中，遞歸調(diào)用的主體函數(shù)為KnapSack，m表示背包的容量，n表示物品的數(shù)量，x[n]表示是否選擇了第n個物品（1—選，0—不選）。每個物品的重量和價值信息分別存放在數(shù)組w[n]和v[n]中。代碼如下:3.貪心法：0-1背包問題與背包問題類似，所不同的是在選擇物品裝入背包時，可以選擇一部分，而不一定要全部裝入背包。這兩類問題都具有最優(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背包問題了。4.動態(tài)規(guī)劃法分析：0-1背包問題可以看作是尋找一個序列，對任一個變量的判斷是決定=1還是=0.在判斷完之后，已經(jīng)確定了，在判斷時，會有兩種情況：背包容量不足以裝入物品i，則=0，背包的價值不增加；背包的容量可以裝下物品i，則=1，背包的價值增加。這兩種情況下背包的總價值的最大者應(yīng)該是對判斷后的價值。令表示在前i個物品中能夠裝入容量為j的背包的物品的總價值，則可以得到如下的動態(tài)規(guī)劃函數(shù)：式（1）說明：把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包，得到的價值均為0.式（2）第一個式子說明：如果第i個物品的重量大于背包的容量，則裝入第i個物品得到的最大價值和裝入第i-1個物品得到的最大價值是相同的，即物品i不能裝入背包中；第二個式子說明：如果第i個物品的重量小于背包的容量，則會有兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為的背包中的價值加上第i個物品的價值；（2）如果第i個物品沒有裝入背包，則背包中物品的價值就是等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。我們可以一步一步的解出我們所需要的解。第一步，只裝入第一個物品，確定在各種情況下背包能得到的最大價值；第二步，只裝入前兩個物品，確定在各種情況下的背包能夠得到的最大價值；一次類推，到了第n步就得到我們所需要的最優(yōu)解了。最后，便是在容量為W的背包中裝入n個物品時取得的最大價值。為了確定裝入背包的具體物品，從的值向前尋找，如果>,說明第n個物品被裝入了背包中，前n-1個物品被裝入容量為的背包中；否則，第n個物品沒有裝入背包中，前n-1個物品被裝入容量為W的背包中。依此類推，直到確定第一個物品是否被裝入背包為止。由此，我們可以得到如下的函數(shù)：.根據(jù)動態(tài)規(guī)劃函數(shù)，用一個的二維數(shù)組C存放中間變量，表示把前i個物品裝入容量為j的背包中獲得的最大價值。設(shè)物品的重量存放在數(shù)組w[n]中，價值存放在數(shù)組v[n]中，背包的容量為W，數(shù)組存放迭代的結(jié)果，數(shù)組x[n]存放裝入背包的物品，動態(tài)規(guī)劃解0-1背包問題的源代碼如下:5.回溯法分析：用回溯法解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≤bestp時，可剪去右子樹。計算右子樹中解的上界可以用的方法是將剩余物品依其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是右子樹中解的上界，用此值來剪枝。為了便于計算上界，可先將物品依其單位重量價值從大到小排序，此后只要順序考察各物品即可。在實現(xiàn)時，由MaxBoundary函數(shù)計算當(dāng)前結(jié)點處的上界。它是類Knap的私有成員。Knap的其他成員記錄了解空間樹種的節(jié)點信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時所需要的?？臻g。在解空間樹的當(dāng)前擴展結(jié)點處，僅當(dāng)要進(jìn)入右子樹時才計算上界函數(shù)MaxBoundary，以判斷是否可以將右子樹減去。進(jìn)入左子樹時不需要計算上界，因為其上界與父結(jié)點的上界相同。在調(diào)用函數(shù)Knapsack之前，需要先將各物品依其單位重量價值從達(dá)到小排序。為此目的，我們定義了類Objiect。其中，運算符與通常的定義相反，其目的是為了方便調(diào)用已有的排序算法。在通常情況下，排序算法將待排序元素從小到大排序。在搜索狀態(tài)空間樹時，由函數(shù)Backtrack控制。在函數(shù)中是利用遞歸調(diào)用的方法實現(xiàn)了空間樹的搜索。具體的代碼如下:6.分支限界法：在解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,level,和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。Bestx[i]=1,當(dāng)且僅當(dāng)最優(yōu)解含有物品i。在類Knap中有四個函數(shù)：上界函數(shù)MaxBoundary(),計算節(jié)點所對應(yīng)價值的上界；函數(shù)AddLiveNode()是將一個新的活結(jié)點插入到子集樹和優(yōu)先隊列中；函數(shù)MaxKnapsack()實施對子集樹的優(yōu)先隊列式分支界限搜索。其中假定物品依其單位價值從大到小已經(jīng)排好序。相應(yīng)的排序過程會在算法的預(yù)處理部分完成。算法中E是當(dāng)前擴展結(jié)點；cw是該結(jié)點的重量；cp是該結(jié)點的價值；up是價值上界。算法的while循環(huán)不斷擴展結(jié)點，直到子集樹的一個葉結(jié)點成為擴展結(jié)點為止。此時優(yōu)先隊列中所有活結(jié)點的價值上界均不超過該葉結(jié)點的價值。因此該葉結(jié)點相應(yīng)的解為問題的最優(yōu)解。在while循環(huán)內(nèi)部，算法首先檢查當(dāng)前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當(dāng)前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當(dāng)右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。函數(shù)Knapsack()完成對輸入數(shù)據(jù)的處理。其主要任務(wù)是將各物品依其單位重量價值從達(dá)到小排好序。然后調(diào)用函數(shù)MaxKnapsack()完成對子集樹的優(yōu)先隊列式分支限界搜索。具體的實現(xiàn)代碼如下:三.時空效率分析1.窮舉法：對于一個有n個元素的集合，其子集數(shù)量為，所以，不論生成子集的算法效率有多高，窮舉法都會導(dǎo)致一個的算法。2.遞歸法：在遞歸法的算法體中有一個if判斷中出現(xiàn)了兩次遞歸調(diào)用比較大小所以它們之間的遞歸關(guān)系式可以大體表示為：，其中表示遞歸法的時間復(fù)雜度，C是常數(shù)。求解遞歸方程可以知道的量級為。所以遞歸法解0-1背包問題的時間復(fù)雜度為。遞歸法是耗費空間最多的算法，每次遞歸調(diào)用都需要壓棧，導(dǎo)致棧的使用很頻繁。3.動態(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）.4.回溯法：由于計算上界的函數(shù)MaxBoundary需要O(n)時間，在最壞情況下有個右兒子結(jié)點需要計算上界，所以解0-1背包問題的回溯法算法BackTrack所需要的計算時間為.5分支限界法：在使用限界分治法時，就是使用更好的限界剪枝函數(shù)使得不必要的解被剔除，但是在最壞情況下的解仍然是和回溯法是相同的。本算法中也是用到了計算上界的函數(shù)MaxBoundary需要O(n)的時間，而且在最壞情況下有個結(jié)點需要計算上界，所以在最壞情況下的時間復(fù)雜度仍然為。四.運行結(jié)果1.窮舉法輸出結(jié)果：2.遞歸法輸出結(jié)果：3.動態(tài)規(guī)劃法輸出結(jié)果：4.回溯法輸出結(jié)果：5.分支限界法輸出結(jié)果：五.分析輸出結(jié)果上面測試的是每種算法在兩種輸入情況下得到的0-1背包問題的解。兩種測試數(shù)據(jù)為：第一組：背包容量：18；物品數(shù)目：7；每個物品重量為：112489610；每個物品價值為：7881213414。第二組：背包容量：50；物品數(shù)目：10；每個物品重量為：81224166935211819；每個物品價值為：34325667543245564670。五種實現(xiàn)的算法中，只有回溯法沒能夠得到預(yù)期的最優(yōu)解。（但是可能是算法設(shè)計時的問題，其實回溯法是窮舉法的變形，肯定能夠得到最優(yōu)解的，這里是我設(shè)計函數(shù)的問題。從遞歸法的輸出可知，它的結(jié)果就是我們想要的最優(yōu)解）。從時間復(fù)雜度和空間復(fù)雜度分析可知，動態(tài)規(guī)劃法的時間復(fù)雜度是最小的，但是同時它的空間復(fù)雜度又是最大的。這里就可以看出在設(shè)計算法的過程中要考慮它們的平衡問題。在時間要求比較快的情況下，我們就可以選擇動態(tài)規(guī)劃法；在空間要求比較高時，我們就可以使用窮舉法或是分枝限界法等其他改進(jìn)的窮舉法。各種算法在解背包問題時的比較如下表所示：算法名稱時間復(fù)雜度優(yōu)點缺點改進(jìn)窮舉法最優(yōu)解速度慢剪枝遞歸法最優(yōu)解空間消耗大用數(shù)組存動態(tài)規(guī)劃法最優(yōu)解速度慢遞歸方程求解貪心法不一定是最優(yōu)解速度快可以作為啟發(fā)回溯法最優(yōu)解速度慢改進(jìn)剪枝分枝限界法最優(yōu)解速度慢優(yōu)化限界函數(shù)從計算復(fù)雜性理論看，背包問題是NP完全問題。半個多世紀(jì)以來，該問題一直是算法與復(fù)雜性研究的熱門話題。通過對0-1背包問題的算法研究可以看出，回溯法和分枝限界法等可以得到問題的最優(yōu)解，可是計算時間太慢；動態(tài)規(guī)劃法也可以得到最優(yōu)解，當(dāng)時，算法需要的計算時間，這與回溯法存在一樣的缺點——計算速度慢；采用貪心算法，雖然耗費上優(yōu)于前者，但是不一定是最優(yōu)解。目前，以上幾種方法中回溯法、動態(tài)規(guī)劃法、貪心法都廣泛