(完整word版)0-1背包問題四種不同算法的實(shí)現(xiàn).

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

2、而使得目標(biāo)函數(shù)達(dá)到最大的那個(gè)可行解則為最優(yōu)解1 。給定 n種物品和 1 個(gè)背包。物品 i的重量是 wi ，其價(jià)值為 pi ，背包的容量為 M 。問應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價(jià)值最大？在選擇裝人背包的物品時(shí)，對(duì)每種物品i 只有兩種選擇，即裝入背包、不裝入背包。不能將物品i 裝人背包多次，也不能只裝入部分的物品i。該問題稱為 0-1 背包問題。0-1 背包問題的符號(hào)化表示是，給定M>0， w i >0 ， pi >0， 1in ，要求找到一個(gè) n 元 0-1 向量向量 (x1， x2xn)， X i =0 或 1 , 1 in,使得xi wi Mxi pi，而

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

4、主要區(qū)別。 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)， 稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、0-1 背包問題的實(shí)現(xiàn)對(duì)于 0-1 背包問題，設(shè) A 是能裝入容量為 c 的背包的具有最大價(jià)值的物品集合，則 Aj=A-j 是 n-1 個(gè)物品 1,2,.,j-1,j+1,.,n 可裝入容量為 c-wj 的背包的具有最大價(jià)值的物品集合。用貪心算法求解0-1 背包問題的步驟是，首先計(jì)算每種物品單位重量的價(jià)值 vi/wi ；然后，將物品進(jìn)行排序，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的

5、物品總量未超過 c，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直進(jìn)行下去，直到背包裝滿為止。3、算法設(shè)計(jì)如下：#include<iostream.h>float#definemax100vmax,wmax,totalv=0,totalw=0/最多物品數(shù),limitw;void sort (int n,float amax,floatcout<<"請(qǐng)輸入 n 和 limitw:"bmax)/按價(jià)值密度排序cin>>n >>limitw;for(i=1;i<=n;i+)int j,h,k;xi=0;floa

6、t t1,t2,t3,cmax;/物品選擇情況表初始化為 0for(k=0;k<n;k+)cout<<"請(qǐng)依次輸入物品的價(jià)值：ck=ak/bk;"<<endl;for(j=0;j<n;j+)for(i=1;i<=n;i+)if(cj<cj+1)cin>>vi;t1=aj;aj=aj+1;aj+1=t1;cout<<endl;t2=bj;bj=bj+1;bj+1=t2;cout<<"請(qǐng)依次輸入物品的重量：t3=cj;cj=cj+1;cj+1=t3;"<<endl

7、;for(i=1;i<=n;i+)cin>>wi;voidknapsack(intn,floatcout<<endl;limitw,floatvmax,floatknapsack (n,limitw,v,w,x);wmax,int xmax)cout<<"the selection is:"floatc1;for(i=1;i<=n;i+)/c1 為背包剩余可裝載重量int i;cout<<xi;sort(n,v,w);if(xi=1)/物品按價(jià)值密度排序totalw=totalw+wi;c1=limitw;tota

8、lv=totalv+vi;for(i=0;i<n;i+)if(wi>c1)break;cout<<endl;xi=1;cout<<" 背 包 的 總 重 量 為 ：/xi 為 1 時(shí)，物品 i 在解中"<<totalw<<endl; / 背包所裝載c1=c1-wi;總重量cout<<" 背 包 的 總 價(jià) 值 為 ："<<totalv<<endl; / 背包的總價(jià)值void main()int n,i,xmax;4、貪心算法運(yùn)行結(jié)果如下圖所示：方案二：動(dòng)態(tài)規(guī)劃

9、算法1、動(dòng)態(tài)規(guī)劃的基本原理與分析動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個(gè)子問題， 先求解子問題，然后從這些子問題的解得到原問題的解。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。前一子問題為后面子問題提供信息，而減少計(jì)算量，最后一個(gè)子問題的解即為問題解。采用此方法求解0-1 背包問題的主要步驟如下：分析最優(yōu)解的結(jié)

10、構(gòu)：最有子結(jié)構(gòu)性質(zhì)；建立遞歸方程；計(jì)算最優(yōu)值；4構(gòu)造最優(yōu)解。2、 0-1 背包問題的實(shí)現(xiàn) 最優(yōu)子結(jié)構(gòu)性質(zhì)0-1 背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè) (y1， y2yn)是所給 0-1 背包問題的一個(gè)最優(yōu)解，則 (y2，y3yn)是下面相應(yīng)子問題的一個(gè)最優(yōu)解：nmaxvk xkk i nwk xkjkixk 0,1, ikn因若不然，設(shè) (z2，z3 zn)是上述問題的一個(gè)最優(yōu)解，而(y2，y3yn)不是它nnvi yiw1y1的最優(yōu)解，由此可見 i 2i 2,且nnv1y1vi zivi yii 2i 1nwi zii 2c。因此nw1y1wi zii2c這說明 (y1， z2zn)是所給0-1

11、背包問題的一個(gè)更優(yōu)解，從而(y1， y2 yn)1 遞歸關(guān)系設(shè)所給 0-1 背包問題的子問題nmaxvk xkk inwk xkjkixk 0,1, ikn的最優(yōu)值為 m(i,j) ，即 m(i,j) 是背包容量為 j，可選擇物品為 i，i+1， ， n 時(shí) 0-1 背包問題的最優(yōu)值。由 0-1 背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i,j) 的遞歸式如下：maxm(i 1), j ),m(i 1, jwi) vi, j wim(i, j)m(i 1, j ),0 jwjvnjwnm(n, j)wn0 j3、算法設(shè)計(jì)如下：#include<iostream>#include&

12、lt;iomanip>using namespace std;const int MAX=1000;intwMAX,vMAX,bestMAX;int VMAXMAX;/ 最大價(jià)值矩陣int W,n;/W為背包的最大載重量， n 為物品的數(shù)量/求最大值函數(shù)int max(int x,int y)return x >= y?x: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 ; j+)Vnj=0;for(j=wn;

13、 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)for(int i=1;i<=n;i+)cin>>wi;V1W=max(V1W,V2W-w1+v1);/生成向量數(shù)組，決定某一個(gè)物品是否應(yīng)該放入背包void Traceback()for(int i=1;

14、 i < n ; i+) /比較矩陣兩鄰兩行 (除最后一行 )，背包容量為 W 的最優(yōu)值 .if(ViW= Vi+1W)/如果當(dāng)前行的最優(yōu)值與下一行的最優(yōu)值相等， 則表明該物品不能放入。besti=0;else/否則可以放入besti=1;W-=wi;memset(V,0,sizeof(V);cout<<" 輸入每件商品的價(jià)值v:"<<endl;for( i=1;i<=n;i+)cin>>vi;Knaspack();/構(gòu)造矩陣 Traceback(); / 求出解的向量數(shù)組int totalW=0;int totalV=0;/

15、顯示可以放入的物品cout<<" 所 選 擇 的 商 品 如下:"<<endl;cout<<" 序 號(hào) i: 重量 w: 價(jià)格 v:"<<endl;for(i=1; i <= n ; i+)if(besti = 1)totalW+=wi;totalV+=vi;cout<<setiosflags(ios:left)<<sebestn=(VnW )?1:0;tw(5)<<i<<""<<wi<<""

16、;<<vi<<endl;void main()cout<<"輸入商品數(shù)量n 和背cout<<" 放入的物品重量總和包容量 W:"是 :"<<totalW<<"價(jià)值最優(yōu)解cin>>n>>W;是:"<<V1W<<"cout<<"輸入每件商品的重量"<<totalV<<endl;w:"<<endl;4、計(jì)算復(fù)雜性分析利用動(dòng)態(tài)規(guī)劃求解 0

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

18、2 n 個(gè)，因此隨著物件數(shù)n 的增大，其解的空間將以n 2 n 級(jí)增長，當(dāng) n 大到一定程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。下一步是組織解空間以便它能被容易地搜索。 典型的組織方法是圖或樹。一旦定義了解空間的組織方法，這個(gè)空間即可按照深度優(yōu)先的方法從開始結(jié)點(diǎn)進(jìn)行搜索，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。2、 0-1 背包問題的實(shí)現(xiàn)回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解( 可能是最優(yōu)的 )。一旦定義了解空間的組織方要選擇一個(gè)對(duì)象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先

19、形成一個(gè)遞歸算法，去找到可獲得的最大收益。然后，對(duì)該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼可找到獲得最大收益時(shí)包含在背包中的對(duì)象的集合。左子樹表示一個(gè)可行的結(jié)點(diǎn)，無論何時(shí)都要移動(dòng)到它，當(dāng)右子樹可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時(shí)，移動(dòng)到它。一種決定是否要移動(dòng)到右子樹的簡單方法是 r為還未遍歷的對(duì)象的收益之和，將r 加到 cp (當(dāng)前節(jié)點(diǎn)所獲收益 )之上，若 (r+cp)目前最優(yōu)解的收益)，則不需搜索右子樹。一種更有bestp(效的方法是按收益密度vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)，就使用它的一部分。3、算法設(shè)計(jì)如下：#inclu

20、de<iostream>w,int c,int n );using namespace std;public:class Knapvoid print()friend int Knapsack(intp,intfor(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)

21、前重量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;/以物品單位重量價(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

22、;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) / 搜索左子樹xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;if(Bound(i+1)>bestp)/ 搜索右子樹xi=0;Backtrack(i+1);class ObjectfriendintKnapsack(intp,intw,int c,int n);public:int operator<=(Object a)constreturn (d>=a.d);private:int ID;float d;intKnapsack(int

23、 p,intw,intc,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 = new intn+1;K.w =

24、 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+)return K.bestp;void main()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

25、 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) ：K.pi=pQi-1.ID;"<<endl;K.wi=wQi-1.ID;for(i=1;i<=n;i+)cin>>wi;K.cp=0;cout<<"最優(yōu)解為(bestx)：K.cw=0;"<<endl;K.c=c;cout<

26、;<"最優(yōu)值為(bestp)：K.n=n;"<<endl;K.bestp=0;cout<<Knapsack(p,w,c,n)<<endl;/回溯搜索cout<<"s重新開始K.Backtrack(1);"<<endl;K.print();cout<<"q退出 "<<endl;delete Q;cin>>k;delete K.w;delete K.p;4、運(yùn)行結(jié)果如下圖所示：方案四：分枝 -限界法1、分枝 -限界法的基本原理與分析分枝限

27、界發(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)?E-結(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 背包問題的實(shí)現(xiàn)0-1 背包問題的最大收益分枝定界算法可以使用定界函數(shù)來計(jì)算活結(jié)點(diǎn)的收益上限 upprofit ，使得以活結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)

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

29、loat d;/ 單位重量價(jià)值class Object;class Object;class bbnodefriendintKnapsack(int*,int*,int ,int ,int *);public:int operator <=(Object a)constfriend Knap;friendintKanpsack(int*,int*,int ,int ,int *);private:bbnode *parent;/指向父節(jié)點(diǎn)return (d >= a.d);的指針bool LChild;/ 左兒子結(jié)點(diǎn)private:標(biāo)志;int*w;/物品重量class HeapN

30、ode數(shù)組int*p;/ 物品價(jià)值friend Knap;數(shù)組public:intcw;/ 當(dāng)前背包operator int () const重量 return uprofit;intcp;/ 當(dāng)前背包void Insert(HeapNode N);價(jià)值void DeleteMax(HeapNode N);int* bestx;/最優(yōu)解的記private:錄數(shù)組int uprofit,/結(jié)點(diǎn)的價(jià)值上界;profit;/ 結(jié)點(diǎn)所對(duì)應(yīng)的/計(jì)算所相應(yīng)的價(jià)值的上界價(jià)值int Knap:MaxBoundary(int i)int weight;/ 結(jié)點(diǎn)所對(duì)應(yīng)的重量int cleft=c-cw;/ 剩余容

31、量int level;/ 活結(jié)點(diǎn)在子集int b=cp;/ 價(jià)值上限樹中所處的層序號(hào)/ 以物品單位重量價(jià)值遞減序bbnode *ptr;/指向活結(jié)點(diǎn)在裝填剩余容量子集樹中相應(yīng)結(jié)點(diǎn)的指針while(i<=n&&wi<=cleft);void HeapNode:Insert(HeapNodecleft-=wi;N)b+=pi;i+;void/將背包的剩余容量裝滿HeapNode:DeleteMax(HeapNodif(i<=n)e N)b+=pi/wi*cleft;return b;class Knap/將一個(gè)新的活結(jié)點(diǎn)插入到子集樹和優(yōu)先隊(duì)列中friend int

32、Knapsack(int*,intvoidKnap:AddLiveNode(int*,int ,int ,int *);up,int cp,int cw,bool ch,int lev)public:int MaxKnapsack();/ 將一個(gè)新的活結(jié)點(diǎn)插入到子private:集樹和最大堆 H 中HeapNode *H;bbnode * b=new bbnode;int MaxBoundary(int i);b->parent=E;void AddLiveNode(intup,intb->LChild=ch;cp,int cw,bool ch,int level);HeapNod

33、e N;bbnode *E;/指向擴(kuò)展N.uprofit=up;結(jié)點(diǎn)的指針N.profit=cp;int c;/背包容量N.weight=cw;int n;/物品總數(shù)N.level=lev;N.ptr=b;cw=N.weight;H->Insert(N);cp=N.profit;up=N.uprofit;/實(shí)施對(duì)子集樹的優(yōu)先隊(duì)列式分i=N.level;支界限搜索int Knap:MaxKnapsack()/ 優(yōu)先隊(duì)列式分支界限法， 返回最大值， bestx 返回最優(yōu)解/定義最大堆的容量為1000H=new HeapNode 1000;/構(gòu)造當(dāng)前最優(yōu)解for(int j=n;j>0;

34、j-)bestxj=E->LChild;E=E->parent;/為 bestx 分配存儲(chǔ)空間bestx=new int n+1;return cp;/初始化int i=1;/對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并完成調(diào)用E=0;MaxKnapsackcw=cp=0;intKnapsack(int p,intw,intint bestp=0;/當(dāng)前最優(yōu)解c,int n,int bestx)int up=MaxBoundary(1);/價(jià)值/ 返回最大值，bestx返回最優(yōu)上界解/搜索子集空間樹/初始化while(i!=n+1)/ 非葉結(jié)點(diǎn)int W=0;/ 裝包物品重量int P=0;/裝包物品價(jià)值/

35、 檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左/ 定義依單位重量價(jià)值排序的兒子結(jié)點(diǎn)物品數(shù)組int wt=cw+wi;if(wt<=c)Object * Q=new Objectn;for(int i=1;i<=n;i+)if(cp+pi>bestp)bestp=cp+pi;/單位重量價(jià)值數(shù)組Qi-1.ID=i;AddLiveNode(up,cp+pi,cw+wi,true,i+1);Qi-1.d=(float)1.0*pi/wi;P+=pi;W+=wi;up=MaxBoundary(i+1);/ 檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右if(W<=c)return P;/ 所有物品兒子結(jié)點(diǎn)if(up>=be

36、stp)裝包/依單位重量價(jià)值排序float f;AddLiveNode(up,cp,cw,false,i+for( i=0;i<n;i+)1);for(int j=i;j<n;j+)/去下一個(gè)擴(kuò)展結(jié)點(diǎn)HeapNode N;if(Qi.d<Qj.d)H->DeleteMax(N);E=N.ptr;f=Qi.d;Qi.d=Qj.d;Qj.d=f;void main()int m,n;/創(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+)int i=0,j=0;int p100,w20

37、,x20;while(1)cout<<"0-1 背包問題遞歸法 "<<endl;K.pi=pQi-1.ID;cout<<" 請(qǐng)輸入背包的容K.wi=wQi-1.ID;量： "<<endl;cout<<"請(qǐng)輸入物品個(gè)數(shù)：K.cp=0;"<<endl;K.cw=0;cout<<" 請(qǐng) 輸入物品的重K.c=c;量： "<<endl;K.n=n;cout<<" 請(qǐng)輸入物品的價(jià)/調(diào)用MaxKnapsack 求

38、問題的值： "<<endl;最優(yōu)解cout<<" 背包的最優(yōu)解int bestp=K.MaxKnapsack();為:"<<endl<<Knapsack(p,w,m,n,for(int j=1;j<=n;j+)x)<<endl;cout<<" 最優(yōu)解條件下選bestxQj-1.ID=K.bestxj;擇的背包為:"<<endl;delete Q;for(i=1;i<=n;i+)delete K.w;cout<<xi<<&quo

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

40、列子問題， 然后從這些子問題中求出原問題的解?；厮萜鋵?shí)就是窮舉，窮舉所有的解，找出解中最優(yōu)的值?；厮莘ㄔ诎瑔栴}的所有解的解空間樹中， 按照深度優(yōu)先的策略， 從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ǖ幕舅悸肥牵捍_定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時(shí)注意剪枝 ,常用的分枝一限界法有最小耗費(fèi)法，最大收益法。 FIFO(先進(jìn)先出 )法等。 0-1 背包問題的分枝一限界算法可以使用最大收益算法。該算法跟回溯法類似。但分枝限界法需要O( 2n )的解空間。故該算法不常用在背包問題求解。 回溯法比分枝限界在占用內(nèi)存方面具有優(yōu)勢(shì)。 回溯法占用的內(nèi)存是 0(解空間的最大路徑長度 )，而

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

42、O( 2n ）法貪心算法O(nlogn）#include<iostream.h>#include<iostream>#include<stdio.h>#include<conio.h>#include<stdlib.h>#define max 100void sort (int n,float amax,float bmax)int j,h,k;float t1,t2,t3,cmax;優(yōu)點(diǎn)缺點(diǎn)改進(jìn)方法可求得最優(yōu)決速度較慢建立動(dòng)態(tài)規(guī)劃策序列遞歸方程判斷右子樹能夠獲得最優(yōu)時(shí)間復(fù)雜度較時(shí)，按效率密解高度 vi/wi 對(duì)剩余對(duì)象排序最大收益或

43、最速度較快，易占用的內(nèi)存較小消耗分枝-求解大，效率不高限界法， FIFO法可以達(dá)到局部不能考慮到整對(duì)范圍廣的問體最優(yōu)解，程最優(yōu)解，用時(shí)題可以產(chǎn)生接序可讀性低于少近的最優(yōu)解動(dòng)態(tài)規(guī)劃/ 最多物品數(shù)/ 按價(jià)值密度排序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

44、c1; int i;/c1為背包剩余可裝載重量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 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<&l

45、t;" 請(qǐng)依次輸入物品的價(jià)值："<<endl;for(i=1;i<=n;i+)cin>>vi;cout<<endl;cout<<" 請(qǐng)依次輸入物品的重量：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;"<<endl;cout<<endl;cout<<" 背包的總重量為：cout<<" 背包的總價(jià)值為："<<totalw<<endl; / "<<totalv<