背包問(wèn)題求解方法綜述

1、-. z.算法分析與設(shè)計(jì)大作業(yè)實(shí)驗(yàn)題目：0-1背包問(wèn)題求解方法綜述組 員： 班級(jí)：指導(dǎo)教師：0-1背包問(wèn)題求解方法綜述【摘要】：0-1背包問(wèn)題是一個(gè)經(jīng)典的NP-hard組合優(yōu)化問(wèn)題，現(xiàn)實(shí)生活中的很多問(wèn)題都可以以它為模型。本文首先對(duì)背包問(wèn)題做了闡述，然后用蠻力解法、動(dòng)態(tài)規(guī)劃算法、貪心算法和回溯解法對(duì)背包問(wèn)題進(jìn)展求解，分析了0-1背包問(wèn)題的數(shù)學(xué)模型,刻劃了最優(yōu)解的構(gòu)造特征,建立了求最優(yōu)值的遞歸關(guān)系式。最后對(duì)四種算法從不同角度進(jìn)展了比照和總結(jié)?！娟P(guān)鍵詞】：0-1背包問(wèn)題；蠻力解法；動(dòng)態(tài)規(guī)劃算法；貪心算法；回溯解法。0.引言0-1背包問(wèn)題是指給定n個(gè)物品,每個(gè)物品均有自己的價(jià)值vi和重量wi(i=1,

2、2,n),再給定一個(gè)背包,其容量為W。要求從n個(gè)物品中選出一局部物品裝入背包,這局部物品的重量之和不超過(guò)背包的容量,且價(jià)值之和最大。單個(gè)物品要么裝入,要么不裝入。很多問(wèn)題都可以抽象成該問(wèn)題模型,如配載問(wèn)題、物資調(diào)運(yùn)1問(wèn)題等,因此研究該問(wèn)題具有較高的實(shí)際應(yīng)用價(jià)值。目前,解決0-1背包問(wèn)題的方法有很多,主要有動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法、遺傳算法、粒子群算法、人工魚(yú)群算法、蟻群算法、模擬退火算法、蜂群算法、禁忌搜索算法等。其中動(dòng)態(tài)規(guī)劃、回溯法、分支限界法時(shí)間復(fù)雜性比擬高,計(jì)算智能算法可能出現(xiàn)局部收斂,不一定能找出問(wèn)題的最優(yōu)解。文中在動(dòng)態(tài)規(guī)劃法的根底上進(jìn)展了改良,提出一種求解0-1背包問(wèn)題的算法,

3、該算法每一次執(zhí)行總能得到問(wèn)題的最優(yōu)解,是確定性算法,算法的時(shí)間復(fù)雜性最壞可能為O(2n)。1.0-1背包問(wèn)題描述0-1背包問(wèn)題(KP01)是一個(gè)著名的組合優(yōu)化問(wèn)題。它應(yīng)用在許多實(shí)際領(lǐng)域,如工程選擇、資源分布、投資決策等。背包問(wèn)題得名于如何選擇最適宜的物品放置于給定背包中。本文主要研究背包問(wèn)題中最根底的0/1背包問(wèn)題的一些解決方法。為解決背包問(wèn)題，大量學(xué)者在過(guò)去的幾十年中提出了很多解決方法。解決背包問(wèn)題的算法有最優(yōu)算法和啟發(fā)式算法2，最優(yōu)算法包括窮舉法、動(dòng)態(tài)規(guī)劃法、分支定界法、圖論法等，啟發(fā)式算法包括貪心算法、遺傳算法、蟻群算法、粒子算法等一些智能算法。0-1背包問(wèn)題一般描述為：給定n種物品和一

4、個(gè)背包。物品i的重量是w(i)，其價(jià)值為v(i)，背包的容量為c。問(wèn)應(yīng)該如何選擇裝入背包的物品，使得裝入背包中的物品的總價(jià)值最大？在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包屢次，也不能只裝入局部的物品i。因此，該問(wèn)題稱為0-1背包問(wèn)題。此問(wèn)題的形式化描述是，給定，要求找出一個(gè)n元0-1向量，使得，而且到達(dá)最大。數(shù)學(xué)模型：約束條件： ， 2.0-1背包問(wèn)題的求解算法2.1蠻力算法brute force method2.1.1根本思想：對(duì)于有n種可選物品的0/1背包問(wèn)題，其解空間由長(zhǎng)度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹(shù)時(shí)，深度優(yōu)

5、先遍歷，搜索每一個(gè)結(jié)點(diǎn)，無(wú)論是否可能產(chǎn)生最優(yōu)解，都遍歷至葉子結(jié)點(diǎn)，記錄每次得到的裝入總價(jià)值，然后記錄遍歷過(guò)的最大價(jià)值。2.1.2代碼實(shí)現(xiàn):#include#includeusing namespace std;#define N 100 /最多可能物體數(shù)struct goods /物品構(gòu)造體 int sign; /物品序號(hào) int w; /物品重量 int p; /物品價(jià)值aN;bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w);int ma*(int a,int b) return an-1) if(bestPcp&cw+ai.w=C) for

6、 (int k=0;kn;k+) *k=c*k;/存儲(chǔ)最優(yōu)路徑 bestP=cp; return bestP; cw=cw+ai.w; cp=cp+ai.p; c*i=1; /裝入背包 Force(i+1); cw=cw-ai.w; cp=cp-ai.p; c*i=0; /不裝入背包 Force(i+1); return bestP;int KnapSack1(int n,goodsa,int C,int *) Force(0); return bestP;int main() goods bN; printf(物品種數(shù)n: ); scanf(%d,&n); /輸入物品種數(shù) printf(背包

7、容量C: ); scanf(%d,&C); /輸入背包容量 for (int i=0;in;i+) /輸入物品i的重量w及其價(jià)值v printf(物品%d的重量w%d及其價(jià)值v%d: ,i+1,i+1,i+1); scanf(%d%d,&ai.w,&ai.p); bi=ai; int sum1=KnapSack1(n,a,C,*);/調(diào)用蠻力法求0/1背包問(wèn)題 printf(蠻力法求解0/1背包問(wèn)題:n*= ); for(i=0;in;i+) cout*i ;/輸出所求*n矩陣 printf( 裝入總價(jià)值%dn,sum1); bestP=0,cp=0,cw=0;/恢復(fù)初始化2.1.3復(fù)雜度分析

8、：蠻力法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為：2n2.2貪心算法Greedy algorithm 貪心算法通過(guò)一系列的選擇來(lái)得到問(wèn)題的解。貪心選擇即它總是做出當(dāng)前最好的選擇4。貪心選擇性質(zhì)指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)選擇，這是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。 貪心算法每次只考慮一步，每一步數(shù)據(jù)的選取都必須滿足局部最優(yōu)條件。在枚舉剩下數(shù)據(jù)與當(dāng)前已經(jīng)選取的數(shù)據(jù)組合獲得的解中，提取其中能獲得最優(yōu)解的唯一的一個(gè)數(shù)據(jù)，參加結(jié)果數(shù)據(jù)中，直到剩下的數(shù)據(jù)不能再參加為止6。貪心算法不能保證得到的最后解是最正確的，也不能用來(lái)求最大或最小解問(wèn)題，只能求滿足*些約束條件的可行解*圍。2.2.1算法設(shè)計(jì)用

9、貪心算法解決0-1背包問(wèn)題一般有以下三種策略：價(jià)值最大者優(yōu)先：在剩余物品中，選出可以裝入背包的價(jià)值最大的物品，假設(shè)背包有足夠的容量，以此策略，然后是下一個(gè)價(jià)值最大的物品。但這種策略背包的承重量不能夠得到有效利用，即得不到最優(yōu)解。例如：n=3,w=50,20,20,v=10,7,7c=55,得到的解是*=1,0,0,這種方案的總價(jià)值為10，而最優(yōu)解為0,1,1,總價(jià)值為14。重量最小者優(yōu)先：在剩余物品中，選擇可以裝入背包的重量最小的物品。但這種策略，不能保證重量小的是最有價(jià)值的，也不能得到最優(yōu)解。例如：n=2,w=10,20,v=5,100,c=25，得到的解為*=1,0,而最優(yōu)解是0,1。單位

10、價(jià)值最大者優(yōu)先：根據(jù)價(jià)值與重量的比值/，即單位價(jià)值，在剩下的物品中依次選取比值最大的物品裝入背包。這種策略也不能得到最優(yōu)解。例如：n=3,w=20,15,15,v=40,25,25,/=2,5/3,5/3,c=30,得到的解*=1,0,0,而最優(yōu)解是0,1,1。但它是直覺(jué)上的一個(gè)近似解。本文討論該策略。策略3的具體步驟為：第一步：計(jì)算每個(gè)物品的價(jià)值比=/，i=1,2,n。第二步：對(duì)物品的價(jià)值比非遞增排序。第三步：重復(fù)下面操作，直到有序列表中留下物品。如果列表中的當(dāng)前物品能夠裝入背包，就將它放入背包中，否則，處理下一個(gè)物品。2.2.2 編程實(shí)現(xiàn)#includestdaf*.h#include #

11、include #includeusing namespacestd;#define ma* 100 /自定義物品最大數(shù)void package(int v,int w,int n,int c) /定義包函數(shù) doubleama*; inti,totalv=0,totalw=0,inde*ma*; for(i=0;in;i+) ai=(double)vi/wi; /單位價(jià)值計(jì)算 inde*i=i; for(i=1;in;i+) for(int j=0;jn-i;j+) if(ajaj+1) /進(jìn)展循環(huán)判斷 double b=aj; aj=aj+1; aj+1=b; int c=vj; vj=v

12、j+1; vj+1=c; int d=wj; wj=wj+1; wj+1=d; int e=inde*j; inde*j=inde*j+1; inde*j+1=e; cout單位價(jià)值：; /輸出單位價(jià)值 for(i=0;in;i+) coutai ; coutendl物品價(jià)值：; /輸出物品價(jià)值 for(i=0;in;i+) coutvit; coutendl物品重量：; /輸出物品重量 for(i=0;in;i+) coutwit; coutendl; double*ma*=0; i=0; while(wi=c) *i=1; c=c-wi; i+; cout所選擇的商品如下:endl;cou

13、t序號(hào)i:t重量w:t價(jià)格v:tendl;/輸出所選擇的商品 for(i=0;in;i+)if(*i=1)totalw=totalw+wi;totalv=totalv+vi;coutinde*i+1twitviendl; cout背包的總重量為：totalwendl; /背包所裝載總重量cout背包的總價(jià)值為：totalvendl; /背包的總價(jià)值int main(void) /主函數(shù)定義 LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0); intn,i,*ma*;in

14、t vma*,wma*,W; /變量的定義coutnW;for(i=0;in;i+)*i=0; /物品選擇情況表初始化為0for(i=0;in;i+)vi=rand()%1000;wi=rand()%1000;cout商品的重量和價(jià)值如下：endl; for(int i=0;in;i+) coutwit; coutviendl; QueryPerformanceCounter(&begin); package(v,w,n,W); /函數(shù)的調(diào)用 QueryPerformanceCounter(&end); cout時(shí)間: (double)(end.QuadPart- begin.QuadPart

15、) / frequency.QuadPart sMn-1c，說(shuō)明第n個(gè)物品被裝入背包，則=1，前n-1個(gè)物品沒(méi)有被裝入背包，則=0，前n-1個(gè)物品被裝入容量為c的背包中。以此類推，知道確定第1個(gè)物品是否被裝入背包為止。由此，得到下面的關(guān)系式：如果Mij=Mi-1j,說(shuō)明第i個(gè)物品沒(méi)有被裝入背包，則=0；如果MijMi-1j,說(shuō)明第i個(gè)物品被裝入背包，則=1，j=j-。按照上述關(guān)系式，從Mnc的值向前倒推，即j初始為c，i初始為n,即可確定裝入背包的具體物品。上述算法需要Onc時(shí)間計(jì)算時(shí)間。不過(guò)上述算法有2個(gè)明顯確實(shí)點(diǎn)。一是算法要求所給物品的重量1in是整數(shù)；二是當(dāng)背包容量c很大時(shí)，算法需要的計(jì)

16、算時(shí)間較多。2.2.2運(yùn)行結(jié)果貪心算法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為：Onm2.4 回溯法Backtracking2.4.1回溯法0-1背包問(wèn)題的實(shí)現(xiàn)回溯法是一種系統(tǒng)地搜索問(wèn)題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)。一旦定義了解空間的組織方要選擇一個(gè)對(duì)象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹(shù)的形狀。首先形成一個(gè)遞歸算法，去找到可獲得的最大收益。然后，對(duì)該算法加以改良，形成代碼。改良后的代碼可找到獲得最大收益時(shí)包含在背包中的對(duì)象的集合。左子樹(shù)表示一個(gè)可行的結(jié)點(diǎn)，無(wú)論何時(shí)都要移動(dòng)到它，當(dāng)右子樹(shù)可能含有

17、比當(dāng)前最優(yōu)解還優(yōu)的解時(shí)，移動(dòng)到它。一種決定是否要移動(dòng)到右子樹(shù)的簡(jiǎn)單方法是r為還未遍歷的對(duì)象的收益之和，將r加到cp(當(dāng)前節(jié)點(diǎn)所獲收益)之上，假設(shè)( r+cp) =bestp(目前最優(yōu)解的收益)，則不需搜索右子樹(shù)。一種更有效的方法是按收益密度vi/wi對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量。2.4.2 編程實(shí)現(xiàn)如下#includestdaf*.h#include#include#include #includeusing namespace std;#defineN 100 /最多可能物體數(shù)structgoods /物品構(gòu)造體int sign; /物品序號(hào)int w; /物品

18、重量int p; /物品價(jià)值aN,bN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int ma*1(int a,intb) /最大函數(shù)定義return an-1)if(bestPcp)for (int k=0;kn;k+) *k=c*k;/存儲(chǔ)最優(yōu)路徑bestP=cp;returnbestP;if(cw+ai.w=W) /進(jìn)入左子樹(shù)cw=cw+ai.w;cp=cp+ai.p;c*ai.sign=1; /裝入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.p; /回溯，進(jìn)入右子樹(shù)c*ai.sign=0; /不裝入背

19、包BackTrack(i+1);return bestP;void KnapSack3(intn,goods a,int C,int*)int totalW=0;for(inti=0;in;i+)*i=0;ai.sign=i;sort(a,a+n,m);/將各物品按單位重量?jī)r(jià)值降序排列BackTrack(0);cout所選擇的商品如下:endl;cout序號(hào)i:t重量w:t價(jià)格v:tendl;for(int i=0;in;i+) /進(jìn)展循環(huán)輸出 if(*i=1)couti+1t;totalW+=bi.w;coutbi.wt;coutbi.pendl;cout放入背包的物品總重量為：totalW

20、;coutendl;cout放入背包的物品總價(jià)值為：bestPendl; int main() /主函數(shù)的定義LARGE_INTEGER begin,end,frequency; QueryPerformanceFrequency(&frequency); srand(time(0); coutnW;for (inti=0;in;i+)/輸入物品i的重量w及其價(jià)值vai.w=rand()%1000;ai.p=rand()%1000;bi=ai;cout物品的重量和價(jià)值分別如下：endl;for (inti=0;in;i+)/輸入物品i的重量w及其價(jià)值vcoutai.w;coutt;coutai

21、.pendl;QueryPerformanceCounter(&begin);KnapSack3(n,a,W,*);/調(diào)用回溯法求0/1背包問(wèn)題QueryPerformanceCounter(&end); cout時(shí)間: (double)(end.QuadPart- begin.QuadPart) / frequency.QuadPart sendl; 2.4.3 運(yùn)行結(jié)果回溯法法的時(shí)間復(fù)雜度為2.5分枝-限界法Branch - threshold method2.5.1 分枝-限界法的根本原理與分析分枝限界法是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-結(jié)點(diǎn)的擴(kuò)大方式。每個(gè)活

22、結(jié)點(diǎn)有且僅有一次會(huì)變成E-結(jié)點(diǎn)。當(dāng)一個(gè)結(jié)點(diǎn)變?yōu)镋-結(jié)點(diǎn)時(shí)，則生成從該結(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新結(jié)點(diǎn)。在生成的結(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出最優(yōu)解的結(jié)點(diǎn)，其余結(jié)點(diǎn)加人活結(jié)點(diǎn)表，然后從表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)E結(jié)點(diǎn)。從活結(jié)點(diǎn)表中取出所選擇的結(jié)點(diǎn)并進(jìn)展擴(kuò)大，直到找到解或活動(dòng)表為空，擴(kuò)大才完畢。2.5.2 分枝限界0-1背包問(wèn)題的實(shí)現(xiàn)首先，要對(duì)輸入數(shù)據(jù)進(jìn)展預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)展排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它參

23、加到子集樹(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ì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問(wèn)題的最優(yōu)值。2.5.3 編程實(shí)現(xiàn)如下#include#includeusing namespace std;#define N 100 /最多可能物體數(shù)struct goods /物品構(gòu)造體 int sign; /物品序號(hào) int w; /物品重量 int p; /物品價(jià)值aN;bool m(goods a,goods b) return (a.p/a.w)(b.p/b.w);int ma*(int a,int b) return aHi/2.

24、b)swap(Hi, Hi/2);elsedone = true;i = i/2; /堆中元素下移void mov_down(HEAP H, intn, int i) bool done = false; if(2*i)=n)while(!done & (i = 2*i) = n)if(i+1 Hi.b)i+;if(Hi/2.bHi.b)swap(Hi/2, Hi);elsedone = true; /往堆中插入結(jié)點(diǎn)void insert(HEAP H, HEAP*, int &n) n+; Hn = *; mov_up(H,n);/刪除堆中結(jié)點(diǎn)void del(HEAP H, int&n,

25、int i) HEAP *, y; * = Hi; y = Hn; n -; if(i=*.b)mov_up(H,i);elsemov_down(H, n, i); /獲得堆頂元素并刪除HEAP del_top(HEAP H, int&n) HEAP * = H1; del(H, n, 1); return *;/計(jì)算分支節(jié)點(diǎn)的上界void bound( KNAPNODE* node,int M, goods a, int n) int i = node-k; float w = node-w; float p = node-p; if(node-wM) / 物體重量超過(guò)背包載重量node-b

26、 = 0; / 上界置為0 elsewhile(w+ai.w=M)&(in) w += ai.w; / 計(jì)算背包已裝入載重p += ai+.p; / 計(jì)算背包已裝入價(jià)值if(ib = p + (M - w)*ai.p/ai.w;elsenode - b = p; /用分支限界法實(shí)現(xiàn)0/1背包問(wèn)題int KnapSack4(int n,goodsa,int C, int *) int i, k = 0; / 堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0 int v; KNAPNODE *node, *ynode, *znode; HEAP *, y, z, *heap; heap = new HEAPn*n;

27、 / 分配堆的存儲(chǔ)空間 for( i=0; in; i+)ai.sign=i; /記錄物體的初始編號(hào) sort(a,a+n,m); / 對(duì)物體按照價(jià)值重量比排序 *node = new KNAPNODE; / 建立父親結(jié)點(diǎn) for( i=0; is1i = false; *node-k = *node-w = *node-p = 0; while(*node-ks1ynode-k = true; / 裝入第k個(gè)物體ynode-w += aynode-k.w; / 背包中物體重量累計(jì)ynode-p += aynode-k.p; / 背包中物體價(jià)值累計(jì)ynode-k +; / 搜索深度+bound(ynode, C, a, n); / 計(jì)算結(jié)點(diǎn)y的上界y.b = ynode-b;y.p = ynode; insert(heap, y, k); /結(jié)點(diǎn)y按上界的值插入堆中znode = new KNAPNODE; / 建立結(jié)點(diǎn)z*znode = *node; /結(jié)點(diǎn)*的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)zznode-k+; / 搜索深度+bound(znode, C, a, n)