背包問(wèn)題四種不同算法的實(shí)現(xiàn)

1、word蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院題 目 0-1背包問(wèn)題算法實(shí)現(xiàn)院 系 數(shù)理院 專業(yè)班級(jí) 信計(jì)09 學(xué)生姓名 雷雪艷 學(xué) 號(hào) 200905130 指導(dǎo)教師 李秦 二一二年 六 月 五 日一、問(wèn)題描述： 1、01背包問(wèn)題：給定n種物品和一個(gè)背包，背包最大容量為M，物品i的重量是wi,其價(jià)值是平Pi，問(wèn)應(yīng)當(dāng)如何選擇裝入背包的物品，似的裝入背包的物品的總價(jià)值最大？背包問(wèn)題的數(shù)學(xué)描述如下：2、要求找到一個(gè)n元向量(x1，x2xn)，在滿足約束條件：情況下，使得目標(biāo)函數(shù)，其中，1in；M>0；wi>0；pi>0。滿足約束條件的任何向量都是一個(gè)可行解，而使得目標(biāo)函數(shù)到達(dá)最大的那個(gè)可行

2、解那么為最優(yōu)解1。 給定n 種物品和1個(gè)背包。物品i 的重量是wi，其價(jià)值為pi，背包的容量為M。問(wèn)應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價(jià)值最大？在選擇裝人背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包、不裝入背包。不能將物品i 裝人背包屢次，也不能只裝入局部的物品i。該問(wèn)題稱為0-1背包問(wèn)題。0-1背包問(wèn)題的符號(hào)化表示是，給定M>0， w i >0， pi >0，1in ，要求找到一個(gè)n元0-1向量向量(x1，x2xn)， X i =0 或1 , 1in, 使得 ，而且到達(dá)最大2。二、解決方案：方案一：貪心算法1、貪心算法的根本原理與分析 貪心算法總是作出在當(dāng)

3、前看來(lái)是最好的選擇，即貪心算法并不從整體最優(yōu)解上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好近似解。貪心算法求解的問(wèn)題一般具有兩個(gè)重要性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)解的選擇，即貪心選擇來(lái)到達(dá)。這是貪心算法可行的第一個(gè)根本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題

4、可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、0-1背包問(wèn)題的實(shí)現(xiàn)對(duì)于0-1背包問(wèn)題，設(shè)A是能裝入容量為c的背包的具有最大價(jià)值的物品集合，那么Aj=A-j是n-1個(gè)物品1,2,.,j-1,j+1,.,n可裝入容量為c-wj的背包的具有最大價(jià)值的物品集合。用貪心算法求解0-1背包問(wèn)題的步驟是，首先計(jì)算每種物品單位重量的價(jià)值vi/wi；然后，將物品進(jìn)行排序，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。假設(shè)將這種物品全部裝入背包后，背包內(nèi)的物品總量未超過(guò)c，那么選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直進(jìn)行下去，直到背包裝滿為止。3、算法設(shè)計(jì)如下：.word#inc

5、lude<iostream.h>#define max 100 /最多物品數(shù)void sort (int n,float amax,float bmax) /按價(jià)值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;k<n;k+)ck=ak/bk;for(j=0;j<n;j+)if(cj<cj+1)t1=aj;aj=aj+1;aj+1=t1;t2=bj;bj=bj+1;bj+1=t2;t3=cj;cj=cj+1;cj+1=t3;void knapsack(int n,float limitw,float vmax,float wma

6、x,int xmax)float c1; /c1為背包剩余可裝載重量int i;sort(n,v,w); /物品按價(jià)值密度排序c1=limitw;for(i=0;i<n;i+)if(wi>c1)break;xi=1; /xi為1時(shí)，物品i在解中c1=c1-wi;void main()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;cout<<"請(qǐng)輸入n和limitw:"cin>>n >>limitw;for(i=1;i<=n;i+)xi=0; /物品選擇情況表初

7、始化為0cout<<"請(qǐng)依次輸入物品的價(jià)值："<<endl;for(i=1;i<=n;i+)cin>>vi;cout<<endl;cout<<"請(qǐng)依次輸入物品的重量："<<endl;for(i=1;i<=n;i+)cin>>wi;cout<<endl;knapsack (n,limitw,v,w,x);cout<<"the selection is:"for(i=1;i<=n;i+)cout<<xi

8、;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;cout<<endl;cout<<"背包的總重量為："<<totalw<<endl; /背包所裝載總重量cout<<"背包的總價(jià)值為："<<totalv<<endl; /背包的總價(jià)值.word4、貪心算法運(yùn)行結(jié)果如下列圖所示：方案二：動(dòng)態(tài)規(guī)劃算法1、動(dòng)態(tài)規(guī)劃的根本原理與分析動(dòng)態(tài)規(guī)劃算法的根本思想是將待求解問(wèn)題分解成假設(shè)干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。但是經(jīng)分

9、解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以防止大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。它把問(wèn)題分為很多子問(wèn)題，按順序求解子問(wèn)題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最正確的結(jié)果舍棄其余。前一子問(wèn)題為后面子問(wèn)題提供信息，而減少計(jì)算量，最后一個(gè)子問(wèn)題的解即為問(wèn)題解。采用此方法求解0-1背包問(wèn)題的主要步驟如下：分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)；建立遞歸方程；計(jì)算最優(yōu)值；構(gòu)造最優(yōu)解4。2、 0-1背包問(wèn)題的實(shí)現(xiàn) 最優(yōu)子結(jié)構(gòu)性質(zhì)0-1背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)(y1，y2y

10、n)是所給0-1背包問(wèn)題的一個(gè)最優(yōu)解，那么(y2，y3yn)是下面相應(yīng)子問(wèn)題的一個(gè)最優(yōu)解：因假設(shè)不然，設(shè)(z2，z3zn)是上述問(wèn)題的一個(gè)最優(yōu)解，而(y2，y3yn)不是它的最優(yōu)解，由此可見(jiàn),且c。因此c這說(shuō)明(y1，z2zn)是所給0-1背包問(wèn)題的一個(gè)更優(yōu)解，從而(y1，y2yn)不是所給0-1背包問(wèn)題的最優(yōu)解。此為矛盾1。 遞歸關(guān)系設(shè)所給0-1背包問(wèn)題的子問(wèn)題 的最優(yōu)值為m(i,j)，即m(i,j)是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i,j)的遞歸式如下：3、算法設(shè)計(jì)如下：.word#include<i

11、ostream>#include<iomanip>using namespace std;const int MAX=1000;int wMAX,vMAX,bestMAX;int VMAXMAX; /最大價(jià)值矩陣int W,n; /W為背包的最大載重量，n為物品的數(shù)量/求最大值函數(shù)int max(int x,int y) return x >= yx:y;/求最小值函數(shù)int min(int x,int y)return x>= y y:x;void Knaspack()int Max=min(wn-1,W); for(int j=1; j <= Max ;

12、 j+)Vnj=0;for( j=wn; j <= W ; j+)Vnj=vn;for(int i=n-1;i > 1 ; i-)Max=min(wi-1,W);for( j=1; j <= Max ; j+)Vij=Vi+1j;for( j=wi; j <= W; j+)Vij=max(Vi+1j,Vi+1j-wi+vi); V1W=V2W; /先假設(shè)第一個(gè)物品不放入if(W > w1) V1W=max(V1W,V2W-w1+v1);/生成向量數(shù)組，決定某一個(gè)物品是否應(yīng)該放入背包void Traceback()for(int i=1; i < n ; i+

13、) /比擬矩陣兩鄰兩行(除最后一行)，背包容量為W的最優(yōu)值.if(ViW = Vi+1W) /如果當(dāng)前行的最優(yōu)值與下一行的最優(yōu)值相等，那么說(shuō)明該物品不能放入。besti=0;else /否那么可以放入besti=1;W-=wi;bestn=(VnW )1:0;void main() cout<<"輸入商品數(shù)量n 和背包容量W:"cin>>n>>W;cout<<"輸入每件商品的重量w:"<<endl;for(int i=1;i<=n;i+)cin>>wi;memset(V,0,s

14、izeof(V);cout<<"輸入每件商品的價(jià)值v:"<<endl;for( i=1;i<=n;i+)cin>>vi;Knaspack();/構(gòu)造矩陣 Traceback(); /求出解的向量數(shù)組int totalW=0;int totalV=0;/顯示可以放入的物品cout<<"所選擇的商品如下:"<<endl;cout<<"序號(hào)i:重量w:價(jià)格v:"<<endl;for(i=1; i <= n ; i+)if(besti = 1)to

15、talW+=wi;totalV+=vi;cout<<setiosflags(ios:left)<<setw(5)<<i<<" "<<wi<<" "<<vi<<endl;cout<<"放入的物品重量總和是:"<<totalW<<" 價(jià)值最優(yōu)解是:"<<V1W<<" "<<totalV<<endl;.word4、計(jì)算復(fù)雜性

16、分析利用動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題的復(fù)雜度為0(minnc,2n。動(dòng)態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時(shí)，可建立動(dòng)態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問(wèn)題8。5、動(dòng)態(tài)規(guī)劃運(yùn)行結(jié)果如下列圖所示：方案三：回溯法1、回溯法的根本原理與分析回溯是一種系統(tǒng)地搜索問(wèn)題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)。回溯法需要為問(wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)。使用遞歸回溯法解決背包問(wèn)題的優(yōu)點(diǎn)在于它算法思想簡(jiǎn)單，而且它能完全遍歷搜索空間，肯定能找到問(wèn)題的最優(yōu)解奉但是由于此問(wèn)題解的總

17、組合數(shù)有個(gè)，因此隨著物件數(shù)n的增大，其解的空間將以n級(jí)增長(zhǎng)，當(dāng)n大到一定程度上，用此算法解決背包問(wèn)題將是不現(xiàn)實(shí)的。下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹(shù)。一旦定義了解空間的組織方法，這個(gè)空間即可按照深度優(yōu)先的方法從開(kāi)始結(jié)點(diǎn)進(jìn)行搜索，利用限界函數(shù)防止移動(dòng)到不可能產(chǎn)生解的子空間。2、 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è)遞歸算法，去找

18、到可獲得的最大收益。然后，對(duì)該算法加以改良，形成代碼。改良后的代碼可找到獲得最大收益時(shí)包含在背包中的對(duì)象的集合。左子樹(shù)表示一個(gè)可行的結(jié)點(diǎn)，無(wú)論何時(shí)都要移動(dòng)到它，當(dāng)右子樹(shù)可能含有比當(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ì)象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)， 就使用它的一局部。3、算法設(shè)計(jì)如下：.word#include<

19、iostream>using namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n );public:void print()for(int m=1;m<=n;m+) cout<<bestxm<<" " cout<<endl;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

20、 cp;/當(dāng)前價(jià)值int bestp;/當(dāng)前最優(yōu)值int *bestx;/當(dāng)前最優(yōu)解int *x;/當(dāng)前解;int Knap:Bound(int i)/計(jì)算上界int cleft=c-cw;/剩余容量int b=cp;/以物品單位重量?jī)r(jià)值遞減序裝入物品while(i<=n&&wi<=cleft) cleft-=wi; b+=pi; i+;/裝滿背包if(i<=n) b+=pi/wi*cleft;return b;void Knap:Backtrack(int i)if(i>n) if(bestp<cp) for(int j=1;j<=n;j+

21、) bestxj=xj; bestp=cp;return;if(cw+wi<=c) /搜索左子樹(shù) xi=1; cw+=wi; cp+=pi; Backtrack(i+1); cw-=wi; cp-=pi; if(Bound(i+1)>bestp)/搜索右子樹(shù) xi=0; Backtrack(i+1); class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator<=(Object a)constreturn (d>=a.d);private:int ID;float d;int

22、Knapsack(int 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;i<n;i+)for(int j=i;j<n;j+) if(Qi.d<Qj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K;K.p =

23、 new 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;void main()int *p;int *w; int c=0;int n=0;int i=0;ch

24、ar k;while(k)cout<<"請(qǐng)輸入背包容量(c)："<<endl;cin>>c;cout<<"請(qǐng)輸入物品的個(gè)數(shù)(n)："<<endl; cin>>n;p=new intn+1;w=new intn+1;p0=0;w0=0;cout<<"請(qǐng)輸入物品的價(jià)值(p)："<<endl;for(i=1;i<=n;i+) cin>>pi;cout<<"請(qǐng)輸入物品的重量(w)："<<

25、endl;for(i=1;i<=n;i+) cin>>wi;cout<<"最優(yōu)解為(bestx)："<<endl;cout<<"最優(yōu)值為(bestp)："<<endl;cout<<Knapsack(p,w,c,n)<<endl; cout<<"s 重新開(kāi)始"<<endl;cout<<"q 退出"<<endl;cin>>k;.word4、運(yùn)行結(jié)果如下列圖所示：方案四：分

26、枝-限界法1、分枝-限界法的根本原理與分析 分枝限界發(fā)是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對(duì)E-結(jié)點(diǎn)(expansion node)的擴(kuò)充方式。每個(gè)活結(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ò)充才結(jié)束。2、0-1背包問(wèn)題的實(shí)現(xiàn)0-1背包問(wèn)題的最大收益分枝定界算法可以使用定界函數(shù)來(lái)計(jì)算活結(jié)點(diǎn)的收益上限upprofit，使得以活結(jié)點(diǎn)為根

27、的子樹(shù)中的任一結(jié)點(diǎn)的收益值都不可能超過(guò)upprofit，活結(jié)點(diǎn)的最大堆使用upprofit作為關(guān)鍵值域。在子集樹(shù)中執(zhí)行最大收益分枝定界搜索的函數(shù)首先初始化活結(jié)點(diǎn)的最大堆，并使用一個(gè)數(shù)組bestx來(lái)記錄最優(yōu)解。由于需要不斷地利用收益密度來(lái)排序，物品的索引值會(huì)隨之變化，因此必須將函數(shù)所生成的結(jié)果映射回初始時(shí)的物品索引。函數(shù)中的循環(huán)首先檢驗(yàn)E-結(jié)點(diǎn)左孩子的可行性，如它是可行的，那么將它參加子集樹(shù)及活結(jié)點(diǎn)隊(duì)列(即最大堆)，僅當(dāng)結(jié)點(diǎn)右子樹(shù)的定界值指明可能找到一個(gè)最優(yōu)解時(shí)才將右孩子參加子集樹(shù)和隊(duì)列中。3、算法設(shè)計(jì)：.word #include <iostream.h>class Knap;cl

28、ass Object;class Objectfriend int Knapsack(int *,int *,int ,int ,int *);public:int operator <=(Object a)constreturn (d >= a.d);private:int ID;float d;/單位重量?jī)r(jià)值;class bbnodefriend Knap;friend int Kanpsack(int *,int *,int ,int ,int *);private:bbnode * parent;/指向父節(jié)點(diǎn)的指針bool LChild; /左兒子結(jié)點(diǎn)標(biāo)志;class He

29、apNodefriend Knap;public:operator int () const return uprofit;void Insert(HeapNode N);void DeleteMax(HeapNode N);private:int uprofit, /結(jié)點(diǎn)的價(jià)值上界profit; /結(jié)點(diǎn)所對(duì)應(yīng)的價(jià)值 int weight; /結(jié)點(diǎn)所對(duì)應(yīng)的重量int level; /活結(jié)點(diǎn)在子集樹(shù)中所處的層序號(hào)bbnode * ptr; /指向活結(jié)點(diǎn)在子集樹(shù)中相應(yīng)結(jié)點(diǎn)的指針;void HeapNode:Insert(HeapNode N)void HeapNode:DeleteMax(Heap

30、Node N)class Knapfriend int Knapsack(int *,int *,int ,int ,int *);public:int MaxKnapsack();private:HeapNode *H;int MaxBoundary(int i);void AddLiveNode(int up,int cp,int cw,bool ch,int level);bbnode * E; /指向擴(kuò)展結(jié)點(diǎn)的指針int c; /背包容量int n; /物品總數(shù)int *w; /物品重量數(shù)組int *p; /物品價(jià)值數(shù)組int cw; /當(dāng)前背包重量int cp; /當(dāng)前背包價(jià)值int

31、 * bestx; /最優(yōu)解的記錄數(shù)組;/計(jì)算所相應(yīng)的價(jià)值的上界int Knap:MaxBoundary(int i)int cleft=c-cw; /剩余容量int b=cp; /價(jià)值上限/以物品單位重量?jī)r(jià)值遞減序裝填剩余容量while(i<=n&&wi<=cleft)cleft-=wi;b+=pi;i+;/將背包的剩余容量裝滿if(i<=n) b+=pi/wi*cleft;return b;/將一個(gè)新的活結(jié)點(diǎn)插入到子集樹(shù)和優(yōu)先隊(duì)列中void Knap:AddLiveNode(int up,int cp,int cw,bool ch,int lev)/將一個(gè)

32、新的活結(jié)點(diǎn)插入到子集樹(shù)和最大堆H中bbnode * b=new bbnode;b->parent=E;b->LChild=ch;HeapNode N;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H->Insert(N);/實(shí)施對(duì)子集樹(shù)的優(yōu)先隊(duì)列式分支界限搜索int Knap:MaxKnapsack()/優(yōu)先隊(duì)列式分支界限法，返回最大值，bestx返回最優(yōu)解/定義最大堆的容量為1000H=new HeapNode 1000;/為bestx分配存儲(chǔ)空間bestx=new int n+1;/初始化int i=1;

33、E=0;cw=cp=0;int bestp=0; /當(dāng)前最優(yōu)解int up=MaxBoundary(1);/價(jià)值上界/搜索子集空間樹(shù)while(i!=n+1)/非葉結(jié)點(diǎn)/檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)int wt=cw+wi;if(wt<=c)if(cp+pi>bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=MaxBoundary(i+1);/檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);/去下一個(gè)擴(kuò)展結(jié)點(diǎn)HeapNode N;H->

34、DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit;i=N.level;/構(gòu)造當(dāng)前最優(yōu)解for(int j=n;j>0;j-)bestxj=E->LChild;E=E->parent;return cp;/對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并完成調(diào)用MaxKnapsackint Knapsack(int p,int w,int c,int n,int bestx)/返回最大值，bestx返回最優(yōu)解/初始化int W=0; /裝包物品重量int P=0; /裝包物品價(jià)值/定義依單位重量?jī)r(jià)值排序的物品數(shù)組Object * Q=new

35、Objectn;for(int i=1;i<=n;i+)/單位重量?jī)r(jià)值數(shù)組Qi-1.ID=i;Qi-1.d=(float)1.0*pi/wi;P+=pi;W+=wi;if(W<=c) return P;/所有物品裝包/依單位重量?jī)r(jià)值排序float f;for( i=0;i<n;i+)for(int j=i;j<n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;/創(chuàng)立類Knap的數(shù)據(jù)成員Knap K;K.p=new int n+1;K.w=new int n+1;for(i=1;i<=n;i+)K.pi=pQi-1.ID;K.

36、wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;/調(diào)用MaxKnapsack求問(wèn)題的最優(yōu)解int bestp=K.MaxKnapsack();for(int j=1;j<=n;j+)bestxQj-1.ID=K.bestxj;delete Q;delete K.w;delete K.p;delete K.bestx;return bestp;void main()int m,n;int i=0,j=0;int p100,w20,x20;while(1)cout<<"0-1背包問(wèn)題遞歸法"<<endl; cout<

37、;<"請(qǐng)輸入背包的容量："<<endl;cout<<"請(qǐng)輸入物品個(gè)數(shù)："<<endl; cout<<"請(qǐng)輸入物品的重量："<<endl; cout<<"請(qǐng)輸入物品的價(jià)值："<<endl; cout<<"背包的最優(yōu)解為:"<<endl<<Knapsack(p,w,m,n,x)<<endl; cout<<"最優(yōu)解條件下選擇的背包為:"

38、;<<endl; for(i=1;i<=n;i+) cout<<xi<<"t" cout<<endl;.word4、運(yùn)行結(jié)果如下列圖所示： 三、四種算法的比擬與分析這四種算法都得到了驗(yàn)證，運(yùn)行結(jié)果證明了算法設(shè)計(jì)是可行的，正確的。通過(guò)對(duì)O-1背包問(wèn)題的算法設(shè)計(jì)及時(shí)間復(fù)雜度分析可以看出。無(wú)論采用貪婪法還是動(dòng)態(tài)規(guī)劃法，都是在約束條件下求解最大值建立數(shù)學(xué)模型算法實(shí)現(xiàn)的過(guò)程；但算法具體實(shí)現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比擬貪婪法和動(dòng)態(tài)規(guī)劃法。前者的時(shí)間復(fù)雜度低于后者，從消耗上而言優(yōu)于后者。但后者的實(shí)現(xiàn)算法可讀性要優(yōu)于前者。動(dòng)

39、態(tài)規(guī)劃算法的根本思想是把原問(wèn)題分解為一系列子問(wèn)題，然后從這些子問(wèn)題中求出原問(wèn)題的解?；厮萜鋵?shí)就是窮舉，窮舉所有的解，找出解中最優(yōu)的值?；厮莘ㄔ诎瑔?wèn)題的所有解的解空間樹(shù)中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)?；厮莘ǖ母舅悸肥牵捍_定解空間，建立解空間樹(shù)，用深度優(yōu)先搜索算法遞歸搜索解空間樹(shù)，并同時(shí)注意剪枝,常用的分枝一限界法有最小消耗法，最大收益法。FIFO(先進(jìn)先出)法等。0-1背包問(wèn)題的分枝一限界算法可以使用最大收益算法。該算法跟回溯法類似。但分枝限界法需要O()的解空間。故該算法不常用在背包問(wèn)題求解?；厮莘ū确种ο藿缭谡加脙?nèi)存方面具有優(yōu)勢(shì)?；厮莘ㄕ加玫膬?nèi)存是0(解空間的最大路徑長(zhǎng)

40、度)，而分枝限界所占用的內(nèi)存為0(解空間大小)。對(duì)于一個(gè)子集空間，回溯法需要0(n)的內(nèi)存空間，而分枝限界那么需要0(2n)的空間。雖然最大收益或最小消耗分枝限界在直覺(jué)上要好于回溯法，并且在許多情況下可能會(huì)比回溯法檢查更少的結(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會(huì)在回溯法超出允許的時(shí)間限制之前就超出了內(nèi)存的限制。通過(guò)以上對(duì)0-1背包問(wèn)題的求解分析，我們可以看到各種算法設(shè)計(jì)方法有各內(nèi)不同的特點(diǎn)，針對(duì)不同的問(wèn)題領(lǐng)域，它們有不同的效率，對(duì)于求解0-1背包問(wèn)題，各算法的時(shí)間復(fù)雜度、優(yōu)缺點(diǎn)以及改良方法的比擬如下表所示：算法時(shí)間復(fù)雜度優(yōu)點(diǎn)缺點(diǎn)改良方法動(dòng)態(tài)規(guī)劃O(minnc,可求得最優(yōu)決策序列速度較慢建立動(dòng)態(tài)規(guī)劃遞歸

41、方程回溯法O(n能夠獲得最優(yōu)解時(shí)間復(fù)雜度較高判斷右子樹(shù)時(shí)，按效率密度vi/wi對(duì)剩余對(duì)象排序分枝-限界法O(速度較快，易求解占用的內(nèi)存較大，效率不高最大收益或最小消耗分枝-限界法，F(xiàn)IFO法貪心算法O(nlogn可以到達(dá)局部最優(yōu)解，用時(shí)少不能考慮到整體最優(yōu)解，程序可讀性低于動(dòng)態(tài)規(guī)劃對(duì)范圍廣的問(wèn)題可以產(chǎn)生接近的最優(yōu)解#include<iostream.h>#include<iostream>#include<stdio.h>#include<conio.h>#include<stdlib.h> #define max 100 /最多物品

42、數(shù)void sort (int n,float amax,float bmax) /按價(jià)值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;k<n;k+)ck=ak/bk;for(j=0;j<n;j+)if(cj<cj+1)t1=aj;aj=aj+1;aj+1=t1;t2=bj;bj=bj+1;bj+1=t2;t3=cj;cj=cj+1;cj+1=t3;void knapsack(int n,float limitw,float vmax,float wmax,int xmax)float c1; int i; /c1為背包剩余可裝載重量so

43、rt(n,v,w); /物品按價(jià)值密度排序c1=limitw;for(i=0;i<n;i+)if(wi>c1)break;xi=1; /xi為1時(shí)，物品i在解中c1=c1-wi;void main1()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;cout<<"請(qǐng)輸入n和總重量:"cin>>n >>limitw;for(i=1;i<=n;i+)xi=0; /物品選擇情況表初始化為0cout<<"請(qǐng)依次輸入物品的價(jià)值："<&

44、lt;endl;for(i=1;i<=n;i+)cin>>vi;cout<<endl;cout<<"請(qǐng)依次輸入物品的重量："<<endl;for(i=1;i<=n;i+)cin>>wi;cout<<endl;knapsack (n,limitw,v,w,x);cout<<"the selection is:"for(i=1;i<=n;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;c

45、out<<endl;cout<<"背包的總重量為："<<totalw<<endl; /背包所裝載總重量cout<<"背包的總價(jià)值為："<<totalv<<endl; /背包的總價(jià)值using namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n );public:void print()for(int m=1;m<=n;m+) cout<<bestxm<<&qu

46、ot; " cout<<endl;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)前解;int Knap:Bound(int i)/計(jì)算上界int cleft=c-cw;/剩余容量int b=cp;/以物品單位重量?jī)r(jià)值遞減序裝入物品while(i<=n&&wi<=clef

47、t) cleft-=wi; b+=pi; i+;/裝滿背包if(i<=n) b+=pi/wi*cleft;return b;void Knap:Backtrack(int i)if(i>n) if(bestp<cp) for(int j=1;j<=n;j+) bestxj=xj; bestp=cp;return;if(cw+wi<=c) /搜索左子樹(shù) xi=1; cw+=wi; cp+=pi; Backtrack(i+1); cw-=wi; cp-=pi; if(Bound(i+1)>bestp)/搜索右子樹(shù) xi=0; Backtrack(i+1); cl

48、ass Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator<=(Object a)constreturn (d>=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,int n)/為Knap:Backtrack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn;for(int i=1;i<=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;

49、if(W<=c) return P;/裝入所有物品/依物品單位重量排序float f;for( i=0;i<n;i+)for(int j=i;j<n;j+) if(Qi.d<Qj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K;K.p = new 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.

50、n=n;K.bestp=0;/回溯搜索K.Backtrack(1); K.print(); delete Q;delete K.w;delete K.p;return K.bestp;void main2()int *p;int *w; int c=0;int n=0;int i=0;char k;while(k)cout<<"請(qǐng)輸入背包容量(c)："<<endl;cin>>c;cout<<"請(qǐng)輸入物品的個(gè)數(shù)(n)："<<endl; cin>>n;p=new intn+1;w=new

51、 intn+1;p0=0;w0=0;cout<<"請(qǐng)輸入物品的價(jià)值(p)："<<endl;for(i=1;i<=n;i+) cin>>pi;cout<<"請(qǐng)輸入物品的重量(w)："<<endl;for(i=1;i<=n;i+) cin>>wi;cout<<"最優(yōu)解為(bestx)："<<endl;cout<<"最優(yōu)值為(bestp)："<<endl;cout<<Knapsa

52、ck(p,w,c,n)<<endl; cout<<"s 重新開(kāi)始"<<endl;cout<<"q 退出"<<endl;cin>>k;class Knap;class Object;class Objectfriend int Knapsack(int *,int *,int ,int ,int *);public:int operator <=(Object a)constreturn (d >= a.d);private:int ID;float d;/單位重量?jī)r(jià)值;class bbnodefri