背包問題求解方法綜述

v1.0 可編輯可修改算法分析與設計大作業(yè)實驗題目：0-1背包問題求解方法綜述組 員：班 級：指導老師：1v1.0 可編輯可修改0-1背包問題求解方法綜述【摘要】：0-1背包問題是一個經典的 NP-hard組合優(yōu)化問題，現(xiàn)實生活中的很多問題都可以以它為模型。本文首先對背包問題做了闡述，然后用蠻力解法、動態(tài)規(guī)劃算法、貪心算法和回溯解法對背包問題進行求解，分析了 0-1背包問題的數學模型,刻劃了最優(yōu)解的結構特征,建立了求最優(yōu)值的遞歸關系式。最后對四種算法從不同角度進行了對比和總結?！娟P鍵詞】：0-1背包問題；蠻力解法；動態(tài)規(guī)劃算法；貪心算法；回溯解法。引言0-1背包問題是指給定n個物品,每個物品均有自己的價值vi和重量wi(i=1,2,?,n),再給定一個背包,其容量為W。要求從n個物品中選出一部分物品裝入背包,這部分物品的重量之和不超過背包的容量,且價值之和最大。單個物品要么裝入,要么不裝入。很多問題都可以抽象成該問題模型 ,如配載問題、物資調運[1]問題等,因此研究該問題具有較高的實際應用價值。目前 ,解決0-1背包問題的方法有很多,主要有動態(tài)規(guī)劃法、回溯法、分支限界法、遺傳算法、粒子群算法、人工魚群算法、蟻群算法、模擬退火算法、蜂群算法、禁忌搜索算法等。其中動態(tài)規(guī)劃、回溯法、分支限界法時間復雜性比較高 ,計算智能算法可能出現(xiàn)局部收斂,不一定能找出問題的最優(yōu)解。文中在動態(tài)規(guī)劃法的基礎上進行了改進 ,提出一種求解 0-1背包問題的算法,該算法每一次執(zhí)行總能得到問題的最優(yōu)解 ,是確定性算法,算法的時間復雜性最壞可能為 O(2n)。背包問題描述0-1背包問題(KP01)是一個著名的組合優(yōu)化問題。它應用在許多實際領域 ,如項目選擇、資源分布、投資決策等。背包問題得名于如何選擇最合適的物品放2v1.0 可編輯可修改置于給定背包中。本文主要研究背包問題中最基礎的0/1背包問題的一些解決方法。為解決背包問題，大量學者在過去的幾十年中提出了很多解決方法。解決背包問題的算法有最優(yōu)算法和啟發(fā)式算法[2]，最優(yōu)算法包括窮舉法、動態(tài)規(guī)劃法、分支定界法、圖論法等，啟發(fā)式算法包括貪心算法、遺傳算法、蟻群算法、粒子算法等一些智能算法。0-1背包問題一般描述為：給定n種物品和一個背包。物品i的重量是w(i)，其價值為v(i)，背包的容量為c。問應該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。此問題的形式化描述是，給定cw，v，in，要求找出一個n0，i0i01nn（x，x，，x），x，inwxc，使得，而且vixiii元0-1向量12ni{0,1}1i1i1達到最大。n數學模型：maxvixii1n約束條件：wixic，xi{0,1},1ini1背包問題的求解算法蠻力算法（bruteforcemethod）基本思想：對于有n種可選物品的0/1背包問題，其解空間由長度為 n的0-1向量組成,可用子集數表示。在搜索解空間樹時，深度優(yōu)先遍歷，搜索每一個結點，無論是否可能產生最優(yōu)解，都遍歷至葉子結點，記錄每次得到的裝入總價值， 然后記錄遍歷過的最大價值。3v1.0 可編輯可修改代碼實現(xiàn):#include<iostream>#include<algorithm>usingnamespacestd;#defineN100<=C){for(intk=0;k<n;k++) X[k]=cx[k];;cp=cp+a[i].p;cx[i]=1; ;cp=cp-a[i].p;cx[i]=0; ,&a[i].p);b[i]=a[i];}intsum1=KnapSack1(n,a,C,X); vi wi vi wi ri vi wi4v1.0 可編輯可修改時，在步驟（3）中計算最優(yōu)解時，通常需記錄更多的信息，以便在步驟（4）中，根據所記錄的信息，快速構造出一個最優(yōu)解。使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃3要素：（1）問題的階段；（2）每個階段的狀態(tài)；（3）從前一個階段轉化后一個階段之間的遞推關系[4]。分析最優(yōu)解的性質，刻畫最優(yōu)解的結構特征——最優(yōu)子結構性質分析設（x1，x2，，xn）所給0-1背包問題的一個最優(yōu)解，則（x2，x3 ，xn）是下面相應子問題的一個最優(yōu)解：n目標函數：maxvixii2n約束條件：wixicw1x1,xi{0,1}(2in)i2證明：若（x2，x3 ，xn）不是上述子問題的一個最優(yōu)解， 而（y2，y3，，yn）是他的nnn最優(yōu)解。由此可知，viyivixi且w1x1wiyic。因此i2i2nnv1x1viy1vixii2i1nw1x1wiyici2這說明（x1，y2，，yn）是原問題的一個更優(yōu)解，從而（y1，y2，，yn）不是所給原問題的最優(yōu)解，產生矛盾。所以（x2，x3 ，xn）是上述子問題的一個最優(yōu)解。遞歸關系由于0-1背包問題的解是用向量（x1，x2，，xn）來描述的。因此，該問題可以看做是決策一個 n元0-1向量（x1，x2，，xn）。對于任意一個分量 xi的決策是“決定xi=1或xi=0，i=1,2,?,n。對xi1決策后，序列(x1，x2，，xi1)已被確定，在決策xi時，問題處于下列兩個狀態(tài)之一：5v1.0 可編輯可修改（1）背包容量不足以裝下物品 i，則=0，裝入背包的價值不增加；（2）背包容量足以裝入物品 i,則=1，裝入背包的價值增加 vi。在這種情況下，裝入背包的價值最大化應該是對決策后的價值。設所給0-1背包問題的子問題nmaxvkxkkin(0,1)，iknwkxkj，xkki的最優(yōu)值為m(i,j), 即m(i,j) 是背包容量為 j，可選擇的物品為 i,i+1, ?,n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結構性質，可以建立計算（mi,j ）的遞歸式為：m(i,j)m(n,j)

max{m(i1,j),m(i1,jwi)vi}(jwi){m(i1,j)(0jw)ivn，jwn{0，0jwn算法設計基于上面的討論，求解 0-1背包的動態(tài)規(guī)劃算法步驟如下：步驟1：當wi(1in)為正整數時，用數組w[n]來存放n個物品的重量；數組v[n]來存放n個物品的價值，背包容量為c，數組M[n+1][c+1]來存放每一次迭代的執(zhí)行結果；數組 x[n]用來存儲所裝入背包的物品狀態(tài)；步驟2：初始化。數組 M的第0行第0列全部設置為0；步驟3：循環(huán)階段。按式（5）確定前i個物品能夠裝入背包的情況下得到的最優(yōu)值；步驟3-1：i=1時，求出M[1][j],1 ≤j≤c；步驟3-2：i=2時，求出M[2][j],1 ≤j≤c；6v1.0 可編輯可修改??步驟3-n:i=n 時，求出M[n][c] 。此時，M[n][c]便是最優(yōu)值；步驟4：確定裝入背包的具體物品。從M[n][c]的值向前推，如果M[n][c]>M[n-1][c]，表明第n個物品被裝入背包，則xn=1，前n-1個物品沒有被裝入背包，則xn=0，前n-1個物品被裝入容量為 c的背包中。以此類推，知道確定第1個物品是否被裝入背包為止。由此，得到下面的關系式：如果M[i][j]=M[i-1][j], 說明第i個物品沒有被裝入背包，則 xi=0；如果M[i][j]>M[i-1][j], 說明第i個物品被裝入背包，則 xi=1，j=j- wi。按照上述關系式，從M[n][c]的值向前倒推，即j初始為c，i初始為n,即可確定裝入背包的具體物品。上述算法需要O（nc）時間計算時間。不過上述算法有2個明顯的確點。一是算法要求所給物品的重量wi（1≤i≤n）是整數；二是當背包容量c很大時，算法需要的計算時間較多。運行結果貪心算法求解0/1背包問題的時間復雜度為： O（nm）7v1.0 可編輯可修改回溯法（Backtracking ）回溯法0-1背包問題的實現(xiàn)回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。一旦定義了解空間的組織方要選擇一個對象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應組織成子集樹的形狀。首先形成一個遞歸算法，去找到可獲得的最大收益。然后，對該算法加以改進，形成代碼。改進后的代碼可找到獲得最大收益時包含在背包中的對象的集合。左子樹表示一個可行的結點，無論何時都要移動到它，當右子樹可能含有比當前最優(yōu)解還優(yōu)的解時，移動到它。一種決定是否要移動到右子樹的簡單方法是r為還未遍歷的對象的收益之和，將r加到cp(當前節(jié)點所獲收益)之上，若(r+cp)<=bestp(目前最優(yōu)解的收益)，則不需搜索右子樹。一種更有效的方法是按收益密度vi/wi對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量。編程實現(xiàn)如下#include""#include<iostream>#include<algorithm>#include<>#include<>usingnamespacestd;#defineN100 <=W){ ;cp=cp+a[i].p;cx[a[i].sign]=1; ;cp=cp-a[i].p; ign]=0; ign=i;}sort(a,a+n,m); ;cout<<b[i].w<<"\t";8v1.0 可編輯可修改cout<<b[i].p<<endl;}}cout<<"放入背包的物品總重量為： "<<totalW;cout<<endl;cout<<"放入背包的物品總價值為： "<<bestP<<endl;}intmain()=rand()%1000;a[i].p=rand()%1000;b[i]=a[i];}cout<<"物品的重量和價值分別如下： "<<endl;for(inti=0;i<n;i++) ;cout<<"\t";cout<<a[i].p<<endl;}QueryPerformanceCounter(&begin);KnapSack3(n,a,W,X); 3運行結果9v1.0 可編輯可修改回溯法法的時間復雜度為分枝-限界法（Branch-thresholdmethod ）分枝-限界法的基本原理與分析分枝限界法是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對 E-結點的擴充方式。每個活結點有且僅有一次會變成 E-結點。當一個結點變?yōu)?E-結點時，則生成從該結點移動一步即可到達的所有新結點。 在生成的結點中，拋棄那些不可能導出最優(yōu)解的結點，其余結點加人活結點表， 然后從表中選擇一個結點作為下一個 E結點。從活結點表中取出所選擇的結點并進行擴充，直到找到解或活動表為空，擴充才結束。分枝限界0-1背包問題的實現(xiàn)首先，要對輸入數據進行預處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中， 節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當前擴展結點的左兒子結點的可行性。 如果該左兒子結點是可行結點， 則將它加入到子集樹和活結點優(yōu)先隊列中。 當前擴展結點的右兒子結點一定是可行結點， 僅當右兒子結點滿足上界約束時才將它加入子集樹和活結點優(yōu)先隊列。 當擴展到葉節(jié)點時為問題的最優(yōu)值。10v1.0 可編輯可修改編程實現(xiàn)如下#include<iostream>#include<algorithm>usingnamespacestd;#defineN100 >H[i/2].b){swap(H[i],H[i/2]);}else{done=true;}i=i/2;}}}>H[i].b){i++;}if(H[i/2].b<H[i].b){swap(H[i/2],H[i]);}else{done=true;}}}}<=M)&&(i<n)){w+=a[i].w;;/a[i].w;}else{11v1.0 可編輯可修改node->b=p;}}}ign=i; ; ; ign]=1;}else{X[a[i].sign]=0;}}deletexnode;deleteheap;returnv; ,&a[i].p);b[i]=a[i];}intsum4=KnapSack4(n,a,C,X); 4運行結果分支限界法求解 0/1背包問題的時間復雜度為：12v1.0 可編輯可修改遺傳算法（Geneticalgorithm ）遺傳算法是模擬達爾文的生物自然選擇學說和自然界的生物進化過程的一種自適應全局概率搜索算法[2]。它是由美國的教授1975年首先提出，其主要特點是直接對結構對象進行操作，不存在求導和函數連續(xù)性的限定；具有內在的隱并行性和良好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調整搜索方向，不需要確定規(guī)則。遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子）進行組合交叉和變異，產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經過解碼，可以作為問題近似最優(yōu)解。算法設計遺傳算法解決0-1背包問題的基本步驟如下：（1）群體的初始化：確定種群規(guī)模 M,交叉概率pc、變異概率pm、染色體長度N即最大進化代數 T。隨機初始化染色體，給出物體體積、物品價值 v和背包容量c。（2）產生遺傳編碼：采用二進制n維矢量解X作為解空間參數的遺傳編碼，串的長度等于n,xi=1表示該物體裝入背包，xi=0表示該物品沒有被裝入背包。（3）適應度函數的構造：適應度函數的建立是解決背包問題的關鍵。 首先背包問題的目標函數和約束條件文章前面已提出n數學模型：maxvixii113v1.0 可編輯可修改n約束條件：wixic，xi{0,1},1ini1現(xiàn)給出構造它的2種適應度函數：n(1)Fvixi,其中xi或（，）10i1,2,ni1nk(2)F(,其中k，其中xi或（，）vixi)1.0012510i1,2,ni1（4）選擇操作：根據選擇概率選擇染色體，將上述的個體作為第一代，采用以正比于適應度的賭輪隨機選擇方式，每個個體適應度值為fi，則i被選中的n概率Pisfi/fi；對于初始化后的種群，先計算出每條染色體的適應度i1值，再計算出其被選擇的概率，將它們進行比較，把選擇概率最小的一條染色體淘汰掉，并選擇概率最大的一條染色體進行復制，用這條復制的染色體代替淘汰的染色體的位置。（5）交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進行交叉，一般采用一點交叉方式，交叉概率為Pc，具體操作是在個體串中隨機設定一個交叉點，實行交叉時，該點前后的兩個個體的部分結構進行互換，并生成兩個新的個體。（6）變異操作：染色體變異采用位點變異的方式。位點變異比較簡單，對于0-1背包問題來說，就是把染色體的變異位1變?yōu)?,0變?yōu)?，其他位保持不變。變異概率為Pm，變異的目的是使其變異后的適應度大于或等于其原適應度。先選擇一個變異位進行變異，再計算它的適應度，看它是否大于或等于其原來的適應度，若不是的話就重新選擇變異位進行變異操作。對種群依次進行選擇、交叉、變異后就檢驗得到的新個體，當某代得到的結果滿足要求或當前代數等于結束代數時算法結束得到結果，否則重新選擇、交叉、變異操作，直到得到滿意的結果為止。使用冪函數適應度函數的遺傳算法全局搜索效率比較高 [2]。14v1.0 可編輯可修改算法分析與比較通過上面幾種算法基本原理的介紹和分析，得到了不同方法解決NP難的0-1背包問題。下面從時間、空間復雜度、準確性等方面進行進一步的分析比較。動態(tài)規(guī)劃算法的空間和時間復雜度由物品的數量和背包的承重量來決定。若物品數量為n,背包承重量為c,初始化數組需要空間為O（nc）,兩重for循環(huán)時間復雜度為O(nc)。動態(tài)規(guī)劃能夠保證求解的正確性，但它速度慢，空間消耗大。貪心算法的時間復雜度為O(nlogn)。但貪心算法屬于近似算法，速度快，時間消耗少，但不能確定結果為最優(yōu)解，體現(xiàn)了該算法的局限性。遺傳算法跟貪心算法一樣，也是一種近似算法。它的時間復雜度取決于采用的適應度函數。第一種適應度函數對遺傳算法的參數比較敏感，冪函數的適應度函數的遺傳函數能獲得高質量的解。算法的效率分析（1）蠻力法對于一個有n個元素的集合，其子集數量為2^n，所以，不論生成子集的算法效率有多高，蠻力法都會導致一個2^n的算法（2）貪心法貪心算法總是作出在當前看來是最好的選擇， 即貪心算法并不從整體最優(yōu)解上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)解。 貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣的許多問題它能產生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解， 但其最終結果卻是最優(yōu)解的很好近似解。貪心算法的時間復雜度為 O(nlogn）。（3）動態(tài)規(guī)劃法從m(i，j)的遞歸式容易看出，算法 Knaspack需要 O(nc)計算時間;Traceback需O(n)計算時間；算法總體需要 O(nc)計算時間。（4）回溯法15v1.0 可編輯可修改由于計算上界函數需要O(n)時間，在最壞情況下有個右孩子結點需要上界函數，故計算0-1背包問題的回溯算法所需的計算時間復雜度為。對回溯法的改進主要是對判斷是否移動右子樹上，一種更有效的方法是按效益密度vi/wi對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量，當遇到第一個不能全部放人背包的對象時，就使用它的一部分?；厮菟惴ǖ倪\行時間取決于它在搜索過程中所生成的結點數,而限界函數可以大量減少所生成的結點個數,省去許多無謂的搜索,使得搜索速度更快,其調用限界函數計算上界需花費O(n)時間,最壞情況下有個結點需調用限界函數,需花費O(n)時間,所以該算法的時間復雜度為。分枝-限界法分支限界法求解0/1背包問題的時間復雜度為：為了直觀表示，特將四種算法的時間復雜度總結如下：（1）為了更好地說明問題，現(xiàn)在對不同問題規(guī)模三種不同算法所需要的時間進行比較。隨著問題規(guī)模的增大，各算法的計算時間都在增大，由于回溯法相對于其他算法所增加的時間更加顯著，特此，單獨考慮回溯法的情況。16v1.0 可編輯可修改（2）此種情況下背包的容量為 100，不同問題規(guī)?；厮莘ㄋ脮r間所下表所示由以上測試時間可以很好的驗證，當背包容量和問題規(guī)模達到一定程度時，用回溯法解決背包問題，因此隨著物件數 n的增大，其解的空間將以 級增長，當n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實的。這正好與理論分析的情況是一致的。6從實驗中也可以發(fā)現(xiàn)，當問題規(guī)模很小的時候，四種算法都有較好的穩(wěn)定性，計算時間都相差不多。隨著問題規(guī)模的增大，各算法的計算時間差別逐漸顯現(xiàn)出來。7對比以上四種算法可以看出，各種算法都有自己的特點，貪心算法速度比較快，但是所得的解有時可能只是局部最優(yōu)解；分枝限界法需要 的解空間。故該算法不常用在背包問題求解；回溯法比分枝限界在占用內存方面具有優(yōu)勢?；厮莘ㄕ加玫膬却媸?(解空間的最大路徑長度)，而分枝限界所占用的內存為0(解空間大小)。對于一個子集空間，回溯法需要0(n)的內存空間，而分枝限界則需要的空間。雖然最大