背包問題求解方法綜述

v1.0 可編輯可修改算法分析與設(shè)計大作業(yè)實(shí)驗(yàn)題目：0-1背包問題求解方法綜述組 員：班 級：指導(dǎo)老師：1v1.0 可編輯可修改0-1背包問題求解方法綜述【摘要】：0-1背包問題是一個經(jīng)典的 NP-hard組合優(yōu)化問題，現(xiàn)實(shí)生活中的很多問題都可以以它為模型。本文首先對背包問題做了闡述，然后用蠻力解法、動態(tài)規(guī)劃算法、貪心算法和回溯解法對背包問題進(jìn)行求解，分析了 0-1背包問題的數(shù)學(xué)模型,刻劃了最優(yōu)解的結(jié)構(gòu)特征,建立了求最優(yōu)值的遞歸關(guān)系式。最后對四種算法從不同角度進(jìn)行了對比和總結(jié)?！娟P(guān)鍵詞】：0-1背包問題；蠻力解法；動態(tài)規(guī)劃算法；貪心算法；回溯解法。引言0-1背包問題是指給定n個物品,每個物品均有自己的價值vi和重量wi(i=1,2,?,n),再給定一個背包,其容量為W。要求從n個物品中選出一部分物品裝入背包,這部分物品的重量之和不超過背包的容量,且價值之和最大。單個物品要么裝入,要么不裝入。很多問題都可以抽象成該問題模型 ,如配載問題、物資調(diào)運(yùn)[1]問題等,因此研究該問題具有較高的實(shí)際應(yīng)用價值。目前 ,解決0-1背包問題的方法有很多,主要有動態(tài)規(guī)劃法、回溯法、分支限界法、遺傳算法、粒子群算法、人工魚群算法、蟻群算法、模擬退火算法、蜂群算法、禁忌搜索算法等。其中動態(tài)規(guī)劃、回溯法、分支限界法時間復(fù)雜性比較高 ,計算智能算法可能出現(xiàn)局部收斂,不一定能找出問題的最優(yōu)解。文中在動態(tài)規(guī)劃法的基礎(chǔ)上進(jìn)行了改進(jìn) ,提出一種求解 0-1背包問題的算法,該算法每一次執(zhí)行總能得到問題的最優(yōu)解 ,是確定性算法,算法的時間復(fù)雜性最壞可能為 O(2n)。背包問題描述0-1背包問題(KP01)是一個著名的組合優(yōu)化問題。它應(yīng)用在許多實(shí)際領(lǐng)域 ,如項目選擇、資源分布、投資決策等。背包問題得名于如何選擇最合適的物品放2v1.0 可編輯可修改置于給定背包中。本文主要研究背包問題中最基礎(chǔ)的0/1背包問題的一些解決方法。為解決背包問題，大量學(xué)者在過去的幾十年中提出了很多解決方法。解決背包問題的算法有最優(yōu)算法和啟發(fā)式算法[2]，最優(yōu)算法包括窮舉法、動態(tài)規(guī)劃法、分支定界法、圖論法等，啟發(fā)式算法包括貪心算法、遺傳算法、蟻群算法、粒子算法等一些智能算法。0-1背包問題一般描述為：給定n種物品和一個背包。物品i的重量是w(i)，其價值為v(i)，背包的容量為c。問應(yīng)該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。此問題的形式化描述是，給定cw，v，in，要求找出一個n0，i0i01nn（x，x，，x），x，inwxc，使得，而且vixiii元0-1向量12ni{0,1}1i1i1達(dá)到最大。n數(shù)學(xué)模型：maxvixii1n約束條件：wixic，xi{0,1},1ini1背包問題的求解算法蠻力算法（bruteforcemethod）基本思想：對于有n種可選物品的0/1背包問題，其解空間由長度為 n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時，深度優(yōu)先遍歷，搜索每一個結(jié)點(diǎn)，無論是否可能產(chǎn)生最優(yōu)解，都遍歷至葉子結(jié)點(diǎn)，記錄每次得到的裝入總價值， 然后記錄遍歷過的最大價值。3v1.0 可編輯可修改代碼實(shí)現(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）中，根據(jù)所記錄的信息，快速構(gòu)造出一個最優(yōu)解。使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃3要素：（1）問題的階段；（2）每個階段的狀態(tài)；（3）從前一個階段轉(zhuǎn)化后一個階段之間的遞推關(guān)系[4]。分析最優(yōu)解的性質(zhì)，刻畫最優(yōu)解的結(jié)構(gòu)特征——最優(yōu)子結(jié)構(gòu)性質(zhì)分析設(shè)（x1，x2，，xn）所給0-1背包問題的一個最優(yōu)解，則（x2，x3 ，xn）是下面相應(yīng)子問題的一個最優(yōu)解：n目標(biāo)函數(shù)：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)解，產(chǎn)生矛盾。所以（x2，x3 ，xn）是上述子問題的一個最優(yōu)解。遞歸關(guān)系由于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。在這種情況下，裝入背包的價值最大化應(yīng)該是對決策后的價值。設(shè)所給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)子結(jié)構(gòu)性質(zhì)，可以建立計算（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算法設(shè)計基于上面的討論，求解 0-1背包的動態(tài)規(guī)劃算法步驟如下：步驟1：當(dāng)wi(1in)為正整數(shù)時，用數(shù)組w[n]來存放n個物品的重量；數(shù)組v[n]來存放n個物品的價值，背包容量為c，數(shù)組M[n+1][c+1]來存放每一次迭代的執(zhí)行結(jié)果；數(shù)組 x[n]用來存儲所裝入背包的物品狀態(tài)；步驟2：初始化。數(shù)組 M的第0行第0列全部設(shè)置為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個物品是否被裝入背包為止。由此，得到下面的關(guān)系式：如果M[i][j]=M[i-1][j], 說明第i個物品沒有被裝入背包，則 xi=0；如果M[i][j]>M[i-1][j], 說明第i個物品被裝入背包，則 xi=1，j=j- wi。按照上述關(guān)系式，從M[n][c]的值向前倒推，即j初始為c，i初始為n,即可確定裝入背包的具體物品。上述算法需要O（nc）時間計算時間。不過上述算法有2個明顯的確點(diǎn)。一是算法要求所給物品的重量wi（1≤i≤n）是整數(shù)；二是當(dāng)背包容量c很大時，算法需要的計算時間較多。運(yùn)行結(jié)果貪心算法求解0/1背包問題的時間復(fù)雜度為： O（nm）7v1.0 可編輯可修改回溯法（Backtracking ）回溯法0-1背包問題的實(shí)現(xiàn)回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。一旦定義了解空間的組織方要選擇一個對象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先形成一個遞歸算法，去找到可獲得的最大收益。然后，對該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼可找到獲得最大收益時包含在背包中的對象的集合。左子樹表示一個可行的結(jié)點(diǎn)，無論何時都要移動到它，當(dāng)右子樹可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時，移動到它。一種決定是否要移動到右子樹的簡單方法是r為還未遍歷的對象的收益之和，將r加到cp(當(dāng)前節(jié)點(diǎn)所獲收益)之上，若(r+cp)<=bestp(目前最優(yōu)解的收益)，則不需搜索右子樹。一種更有效的方法是按收益密度vi/wi對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量。編程實(shí)現(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運(yùn)行結(jié)果9v1.0 可編輯可修改回溯法法的時間復(fù)雜度為分枝-限界法（Branch-thresholdmethod ）分枝-限界法的基本原理與分析分枝限界法是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對 E-結(jié)點(diǎn)的擴(kuò)充方式。每個活結(jié)點(diǎn)有且僅有一次會變成 E-結(jié)點(diǎn)。當(dāng)一個結(jié)點(diǎn)變?yōu)?E-結(jié)點(diǎn)時，則生成從該結(jié)點(diǎn)移動一步即可到達(dá)的所有新結(jié)點(diǎn)。 在生成的結(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出最優(yōu)解的結(jié)點(diǎn)，其余結(jié)點(diǎn)加人活結(jié)點(diǎn)表， 然后從表中選擇一個結(jié)點(diǎn)作為下一個 E結(jié)點(diǎn)。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動表為空，擴(kuò)充才結(jié)束。分枝限界0-1背包問題的實(shí)現(xiàn)首先，要對輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊列分支限界法中， 節(jié)點(diǎn)的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。 如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)， 則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊列中。 當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)， 僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊列。 當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時為問題的最優(yōu)值。10v1.0 可編輯可修改編程實(shí)現(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運(yùn)行結(jié)果分支限界法求解 0/1背包問題的時間復(fù)雜度為：12v1.0 可編輯可修改遺傳算法（Geneticalgorithm ）遺傳算法是模擬達(dá)爾文的生物自然選擇學(xué)說和自然界的生物進(jìn)化過程的一種自適應(yīng)全局概率搜索算法[2]。它是由美國的教授1975年首先提出，其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和良好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定規(guī)則。遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度大小選擇個體，并借助于自然遺傳學(xué)的遺傳算子）進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解。算法設(shè)計遺傳算法解決0-1背包問題的基本步驟如下：（1）群體的初始化：確定種群規(guī)模 M,交叉概率pc、變異概率pm、染色體長度N即最大進(jìn)化代數(shù) T。隨機(jī)初始化染色體，給出物體體積、物品價值 v和背包容量c。（2）產(chǎn)生遺傳編碼：采用二進(jìn)制n維矢量解X作為解空間參數(shù)的遺傳編碼，串的長度等于n,xi=1表示該物體裝入背包，xi=0表示該物品沒有被裝入背包。（3）適應(yīng)度函數(shù)的構(gòu)造：適應(yīng)度函數(shù)的建立是解決背包問題的關(guān)鍵。 首先背包問題的目標(biāo)函數(shù)和約束條件文章前面已提出n數(shù)學(xué)模型：maxvixii113v1.0 可編輯可修改n約束條件：wixic，xi{0,1},1ini1現(xiàn)給出構(gòu)造它的2種適應(yīng)度函數(shù)：n(1)Fvixi,其中xi或（，）10i1,2,ni1nk(2)F(,其中k，其中xi或（，）vixi)1.0012510i1,2,ni1（4）選擇操作：根據(jù)選擇概率選擇染色體，將上述的個體作為第一代，采用以正比于適應(yīng)度的賭輪隨機(jī)選擇方式，每個個體適應(yīng)度值為fi，則i被選中的n概率Pisfi/fi；對于初始化后的種群，先計算出每條染色體的適應(yīng)度i1值，再計算出其被選擇的概率，將它們進(jìn)行比較，把選擇概率最小的一條染色體淘汰掉，并選擇概率最大的一條染色體進(jìn)行復(fù)制，用這條復(fù)制的染色體代替淘汰的染色體的位置。（5）交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染色體進(jìn)行交叉，一般采用一點(diǎn)交叉方式，交叉概率為Pc，具體操作是在個體串中隨機(jī)設(shè)定一個交叉點(diǎn)，實(shí)行交叉時，該點(diǎn)前后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新的個體。（6）變異操作：染色體變異采用位點(diǎn)變異的方式。位點(diǎn)變異比較簡單，對于0-1背包問題來說，就是把染色體的變異位1變?yōu)?,0變?yōu)?，其他位保持不變。變異概率為Pm，變異的目的是使其變異后的適應(yīng)度大于或等于其原適應(yīng)度。先選擇一個變異位進(jìn)行變異，再計算它的適應(yīng)度，看它是否大于或等于其原來的適應(yīng)度，若不是的話就重新選擇變異位進(jìn)行變異操作。對種群依次進(jìn)行選擇、交叉、變異后就檢驗(yàn)得到的新個體，當(dāng)某代得到的結(jié)果滿足要求或當(dāng)前代數(shù)等于結(jié)束代數(shù)時算法結(jié)束得到結(jié)果，否則重新選擇、交叉、變異操作，直到得到滿意的結(jié)果為止。使用冪函數(shù)適應(yīng)度函數(shù)的遺傳算法全局搜索效率比較高 [2]。14v1.0 可編輯可修改算法分析與比較通過上面幾種算法基本原理的介紹和分析，得到了不同方法解決NP難的0-1背包問題。下面從時間、空間復(fù)雜度、準(zhǔn)確性等方面進(jìn)行進(jìn)一步的分析比較。動態(tài)規(guī)劃算法的空間和時間復(fù)雜度由物品的數(shù)量和背包的承重量來決定。若物品數(shù)量為n,背包承重量為c,初始化數(shù)組需要空間為O（nc）,兩重for循環(huán)時間復(fù)雜度為O(nc)。動態(tài)規(guī)劃能夠保證求解的正確性，但它速度慢，空間消耗大。貪心算法的時間復(fù)雜度為O(nlogn)。但貪心算法屬于近似算法，速度快，時間消耗少，但不能確定結(jié)果為最優(yōu)解，體現(xiàn)了該算法的局限性。遺傳算法跟貪心算法一樣，也是一種近似算法。它的時間復(fù)雜度取決于采用的適應(yīng)度函數(shù)。第一種適應(yīng)度函數(shù)對遺傳算法的參數(shù)比較敏感，冪函數(shù)的適應(yīng)度函數(shù)的遺傳函數(shù)能獲得高質(zhì)量的解。算法的效率分析（1）蠻力法對于一個有n個元素的集合，其子集數(shù)量為2^n，所以，不論生成子集的算法效率有多高，蠻力法都會導(dǎo)致一個2^n的算法（2）貪心法貪心算法總是作出在當(dāng)前看來是最好的選擇， 即貪心算法并不從整體最優(yōu)解上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)解。 貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣的許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解， 但其最終結(jié)果卻是最優(yōu)解的很好近似解。貪心算法的時間復(fù)雜度為 O(nlogn）。（3）動態(tài)規(guī)劃法從m(i，j)的遞歸式容易看出，算法 Knaspack需要 O(nc)計算時間;Traceback需O(n)計算時間；算法總體需要 O(nc)計算時間。（4）回溯法15v1.0 可編輯可修改由于計算上界函數(shù)需要O(n)時間，在最壞情況下有個右孩子結(jié)點(diǎn)需要上界函數(shù)，故計算0-1背包問題的回溯算法所需的計算時間復(fù)雜度為。對回溯法的改進(jìn)主要是對判斷是否移動右子樹上，一種更有效的方法是按效益密度vi/wi對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個不能全部放人背包的對象時，就使用它的一部分?；厮菟惴ǖ倪\(yùn)行時間取決于它在搜索過程中所生成的結(jié)點(diǎn)數(shù),而限界函數(shù)可以大量減少所生成的結(jié)點(diǎn)個數(shù),省去許多無謂的搜索,使得搜索速度更快,其調(diào)用限界函數(shù)計算上界需花費(fèi)O(n)時間,最壞情況下有個結(jié)點(diǎn)需調(diào)用限界函數(shù),需花費(fèi)O(n)時間,所以該算法的時間復(fù)雜度為。分枝-限界法分支限界法求解0/1背包問題的時間復(fù)雜度為：為了直觀表示，特將四種算法的時間復(fù)雜度總結(jié)如下：（1）為了更好地說明問題，現(xiàn)在對不同問題規(guī)模三種不同算法所需要的時間進(jìn)行比較。隨著問題規(guī)模的增大，各算法的計算時間都在增大，由于回溯法相對于其他算法所增加的時間更加顯著，特此，單獨(dú)考慮回溯法的情況。16v1.0 可編輯可修改（2）此種情況下背包的容量為 100，不同問題規(guī)模回溯法所用時間所下表所示由以上測試時間可以很好的驗(yàn)證，當(dāng)背包容量和問題規(guī)模達(dá)到一定程度時，用回溯法解決背包問題，因此隨著物件數(shù) n的增大，其解的空間將以 級增長，當(dāng)n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。這正好與理論分析的情況是一致的。6從實(shí)驗(yàn)中也可以發(fā)現(xiàn)，當(dāng)問題規(guī)模很小的時候，四種算法都有較好的穩(wěn)定性，計算時間都相差不多。隨著問題規(guī)模的增大，各算法的計算時間差別逐漸顯現(xiàn)出來。7對比以上四種算法可以看出，各種算法都有自己的特點(diǎn)，貪心算法速度比較快，但是所得的解有時可能只是局部最優(yōu)解；分枝限界法需要 的解空間。故該算法不常用在背包問題求解；回溯法比分枝限界在占用內(nèi)存方面具有優(yōu)勢。回溯法占用的內(nèi)存是0(解空間的最大路徑長度)，而分枝限界所占用的內(nèi)存為0(解空間大小)。對于一個子集空間，回溯法需要0(n)的內(nèi)存空間，而分枝限界則需要的空間。雖然最大