1、The compare of the algorithms for solving 0/1 knapsack problems解決0/1背包問(wèn)題算法比較 0/1背包問(wèn)題概述 在0/1背包問(wèn)題中，需對(duì)容量為c的背包進(jìn)行裝載。從n個(gè)物品中選取裝入背包的物品，每件物品 i的重量為wi, 價(jià)值為pi。對(duì)于可行的背包裝載，背包中的物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即 取得最大值。約束條件為 c和 。 在這個(gè)表達(dá)式中，需求出xi的值。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。niiixp1niiixw1nixi11 , 0動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題l動(dòng)態(tài)規(guī)

2、劃原理：動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。l動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。 動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題l在0/1背包問(wèn)題中需要決定x1xn的值。假設(shè)按i=1，2，,n的次序來(lái)確定xi的值。如果置x1=0，則問(wèn)題轉(zhuǎn)變?yōu)橄鄬?duì)于其余物品，背包容量仍為c的背包問(wèn)題。若置x1=1，問(wèn)題就變?yōu)殛P(guān)于最大背包容量為 c-w1的問(wèn)題?，F(xiàn)設(shè)r c，

3、c-w1為剩余的背包容量。動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題l在第一次決策之后，剩下的問(wèn)題便是考慮背包容量為r時(shí)的決策。不管x1是0或者1，x2，xn必須第一次決策之后的一個(gè)最優(yōu)方案，如果不是，則會(huì)有一個(gè)更好的方案y2，yn，因而x1，y2，yn是一個(gè)更好的方案。動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題l最優(yōu)決策序列由最優(yōu)決策子序列組成。假設(shè)f（i，y）表示剩余容量y，剩余物品為i，i+1，n時(shí)的最優(yōu)解的值，即： pn y=wn f（n，y）= 0 0=y=wi f（i，y）= f(i+1,y) 0=ywi動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題l利用最優(yōu)序列由最優(yōu)子序列構(gòu)成的結(jié)論，可得到f的遞歸式。f（1，c）是初始時(shí)背包問(wèn)題

4、的最優(yōu)解。可使用一式通過(guò)遞歸或迭代來(lái)求解f（1，c）。從f（n，*）開始迭式，f（n，*）由一式得出，然后由二式遞歸計(jì)算f（1，*）（i=n-1,n-2,2）, 最后由二式得出f（1，c）。貪婪算法解決0/1背包問(wèn)題l從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。貪婪算法解決0/1背包問(wèn)題l另一種方案是重量貪婪策略：從剩下的物品中選擇可以裝入背包的重量最小的物品。在一般情況下不一定能得到最優(yōu)解。貪婪算法解決0/1背包問(wèn)題l還可以利用另一方案，價(jià)值密度pi/wi貪婪

5、算法，這種選擇準(zhǔn)則為：從剩余物品種選擇可以裝入包的價(jià)值密度最大的物品，這種策略也不能保證得到最優(yōu)解。貪婪算法解決0/1背包問(wèn)題l可以建立貪婪啟發(fā)式方法來(lái)提供解，使解的結(jié)果與最優(yōu)解的值之差在最優(yōu)解的x%（x0時(shí)總的時(shí)間開銷為O( )。kn1kn貪婪算法解決0/1背包問(wèn)題600種隨機(jī)測(cè)試的統(tǒng)計(jì)結(jié)果偏差百分比k0 1% 5% 10% 25%012239 390 528 583 600360 527 598 600483 581 600回溯法解決0/1背包問(wèn)題 回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問(wèn)題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解

6、空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來(lái)求問(wèn)題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問(wèn)題。 回溯法解決0/1背包問(wèn)題三個(gè)對(duì)象的背包問(wèn)題的解空間三個(gè)對(duì)象的背包問(wèn)題的解空間 1 0 1 0 1 0 1 0 1 0 1 0 1 0ABKGIFHEJNMLDCQ回溯法解決0/1背

7、包問(wèn)題l運(yùn)用回溯法解題通常包含以下三個(gè)步驟： a. 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間； b. 確定易于搜索的解空間結(jié)構(gòu)； c. 以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；回溯法解決0/1背包問(wèn)題l考察如下背包問(wèn)題：n=3，w=20，15，15，p=40，25，25且c=30.回溯法解決0/1背包問(wèn)題l#includelusing namespace std; class Knapfriend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestx

8、m ; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品數(shù) int *w;/物品重量數(shù)組 int *p;/物品價(jià)值數(shù)組 int cw;/當(dāng)前重量 int cp;/當(dāng)前價(jià)值 int bestp;/當(dāng)前最優(yōu)值 int *bestx;/當(dāng)前最優(yōu)解 int *x;/當(dāng)前解; 回溯法解決0/1背包問(wèn)題lint Knap:Bound(int i) /計(jì)算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品單位重量?jī)r(jià)值遞減序裝入物品 while(i=n&wi

9、=cleft) cleft-=wi; b+=pi; i+; /裝滿背包 if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子樹 xi=0; Backtrack(i+1); 回溯法解決0/1背包問(wèn)題lclass Object friend int Knapsack(int p,int w,int c,int n);public: int operator=a.d); lprivate: int ID; float d;回溯法解決0/1背包問(wèn)題lint Knapsack(int

10、 p,int w,int c,int n) /為Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/裝入所有物品 /依物品單位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; 回溯法解決0/1背包問(wèn)題lKnap K; K.p = ne

11、w intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; delete K.p; return K.bestp;l分枝定界法解決0/1背包問(wèn)題l分枝限界法的基本思想 1. 分枝限界法與回溯法的不同

12、（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分枝限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 （2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分枝限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹分枝定界法解決0/1背包問(wèn)題2. 分枝限界法基本思想 分枝限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹。 在分枝限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)

13、點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 分枝定界法解決0/1背包問(wèn)題3. 常見(jiàn)的兩種分枝限界法（1）隊(duì)列式(FIFO)分枝限界法 按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 （2）優(yōu)先隊(duì)列式分枝限界法 按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。分枝定界法解決0/1背包問(wèn)題l0-1背包問(wèn)題背包問(wèn)題l算法的思想 首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。 在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下

14、的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。 算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問(wèn)題的最優(yōu)值分枝定界法解決0/1背包問(wèn)題l下面比較分別利用FIFO分枝定界和最大收益分枝定界方法來(lái)解決如下背包問(wèn)題： n=3，w=20，15，15，p=40，25，25，c=30分枝定界法解決0/1背包問(wèn)題上界函數(shù)while (i = n & wi = cleft) / n表示物品總數(shù)，cleft為剩余空間 cleft -= wi; /wi表示i所占空間 b += pi; /pi表示i的價(jià)值 i+; if (i = n) b += pi / wi * cleft; / 裝填剩余容量裝滿背包return b; /b為上界函數(shù)分枝定界法解決0/1背包問(wèn)題lwhile (i !=