0-1背包問題四種不同算法的實現(xiàn)要點

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

2、則為最優(yōu)解。給定n種物品和1個背包。物品i的重量是wi，其價值為pi，背包的 容量為M。問應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價值最 大？在選擇裝人背包的物品時，對每種物品i只有兩種選擇，即裝入背包、不裝入背包。不能將物品i裝人背包多次，也不能只裝入部分的物品i。該 問題稱為0-1背包問題。0-1背包問題的符號化表示是，給定 M0， w i 0， pi 0，1勻蘭n， 要求找到一個n元0-1向量向量（x1，x2xn）， X i =0或1 ,仁2 n,使得 wi - Mv xi pi，而且2達到最大2。、解決方案：方案一：貪心算法1、貪心算法的基本原理與分析貪心算法總是作出在當前看來是

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

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

5、e#defi nemax100最多物品數(shù)void sort (i nt n, float amax,float bmax)按價值密度排序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(cjcj+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;voidkn apsack(i ntn floatlimitw,floatvmax,floatwmax,i nt xmax)floatc1;c1為背包剩余可裝載重量in

6、t i;sort( n, v,w);物品按價值密度排序c1=limitw;for(i=0;ic1)break;xi=1;/xi為1時，物品i在解中c1= c1-wi;void mai n()int n ,i,xmax;float vmax,wmax,totalv=O,totalw=O ,limitw;cout請輸入 n 和 limitw:; cinn limitw;for(i=1;i=n ;i+)xi=0;物品選擇情況表初始化為0 cout請依次輸入物品的價值： e ndl;for(i=1;i vi;coute ndl;cout請依次輸入物品的重量：e ndl;for(i=1;i wi;cou

7、te ndl;kn apsack (n ,limitw,v,w,x); coutthe selectio n is:; for(i=1;i=n ;i+)cout i vi yiw1y1 、 wi zi的最優(yōu)解，由此可見 *7，且 乞Co因此nnv1y1 亠二 VjZj二 Vj yii =2i =1wlyl WiZiy wim(i,j)=km(i+1,j),0 jcwjvnj wnm(n,j)=幕0 j w n3、算法設(shè)計如下：#in clude#i ncludevioma nip using n amespace std;const int MAX=1000;int wMAX,vMAX,bes

8、tMAX;int VMAXMAX; /最大價 值矩陣int W,n;/W為背包的最大載重量，n為物品 的數(shù)量求最大值函數(shù)int max(i nt x,i nt y)retur n x = y?x:y;求最小值函數(shù)int min (i nt x,i nt y)retur n x= y ? y:x;void Kn aspack()int Max=mi n(w n-1,W);for(i nt j=1; j = Max ; j+)V nj=0;for( j=wn; j 1 ; i-)Max=mi n(wi-1,W);for( j=1; j = Max ; j+)Vij=Vi+1j;for( j=wi;

9、 j w1)V1W=max(V1W,V2 W-w1+v1);生成向量數(shù)組，決定某一個物 品是否應(yīng)該放入背包void Traceback()for(i nt i=1; i nW;coutvv輸入每件商品的重量for(int i=1;i wi;memset(V0,sizeof(V);coutvv輸入每件商品的價值 v:e ndl;for( i=1;i vi;Kn aspack();構(gòu)造矩陣 Traceback(); /求出解的向 量數(shù)組int totalW=0;int totalV=0;顯示可以放入的物品coutvv所選擇的商品如 下:vve ndl;coutvv序號i:重量 w:價格 v:vve

10、 ndl;for(i=1; i v= n ; i+)if(besti = 1)totalW+=wi; totalV+=vi;coutvvsetiosflags(ios:left)vvse tw(5) vvivvvvwivvvvvivve ndl;coutvv放入的物品重量總和 是:vvtotalWvv 價值最優(yōu)解 是:vvV1WvvvvtotalVvve ndl;方案三：回溯法1、回溯法的基本原理與分析回溯是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問題 定義一個解空間，這個解空間必須至少包含問題的一個解（可能是最優(yōu)的）。回溯法需要為問題定義一個解空間，這個解空間必須至少包含問題的

11、一個解 （可能是最優(yōu)的）。使用遞歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單， 而且它能完全遍歷搜索空間，肯定能找到問題的最優(yōu)解奉但是由于此問題解的總組合數(shù)有2n個,因此隨著物件數(shù)n的增大，其解的空間將以門2級增長,當n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實的。下一步是組織解空間以便它能被容易地搜索。 典型的組織方法是圖或樹。 一旦定義了解空間的組織方法，這個空間即可按照深度優(yōu)先的方法從開始結(jié) 點進行搜索，利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。2、0-1背包問題的實現(xiàn)回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為 問題定義一個解空間，這個解空間必須至少包含問題的一

12、個解（可能是最優(yōu)的）。一旦定義了解空間的組織方要選擇一個對象的子集，將它們裝人背包， 以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先形成一個遞歸 算法，去找到可獲得的最大收益。然后，對該算法加以改進，形成代碼。改 進后的代碼可找到獲得最大收益時包含在背包中的對象的集合。左子樹表示一個可行的結(jié)點，無論何時都要移動到它，當右子樹可能含 有比當前最優(yōu)解還優(yōu)的解時，移動到它。一種決定是否要移動到右子樹的簡 單方法是r為還未遍歷的對象的收益之和，將 r加到cp （當前節(jié)點所獲收益） 之上，若（葉cp）乞bestp（目前最優(yōu)解的收益），則不需搜索右子樹。一種更有 效的方法是按收益密度vi/wi對剩

13、余對象排序，將對象按密度遞減的順序去填 充背包的剩余容量，當遇到第一個不能全部放人背包的對象時，就使用它的一部分。3、算法設(shè)計如下：w,i nt c,i nt n ); public:void prin t()for(i nt m=1;m v=n; m+)#in clude using n amespace std; class Knapfriend int Knapsack(int p,intcoutbestxmvv; coute ndl;；private:int Boun d(i nt i);void Backtrack nt i);in t c;/背包容量int n; /物品數(shù)int *

14、w;物品重量數(shù)組 int *p;物品價值數(shù)組 int cw;當前重量 in t cp;/當前價值 int bestp;/當前最優(yōu)值 int *bestx;/當前最優(yōu)解 int *x;當前解;int Kn ap:Bo un d(i nt i)計算上界in t cleft=c-cw; 剩余容量int b=cp;以物品單位重量價值遞減序裝 入物品while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;裝滿背包if(i n)if(bestpcp)for(i nt j=1;j=n ;j+) bestxj=xj; return; if(cw+wibestp) 搜索右 子樹xi=0;Ba

15、cktrack(i+1);class Objectfriend int Knapsack(int p,int w,i nt c,i nt n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,i nt 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;/裝入

16、所有物品/依物品單位重量排序float f;for( i=0;i n ;i+)for(i nt j=i;j n;j+)if(Qi.dQj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;Knap K;K.p = new intn+1;K.w = new in t n+1;K.x = new intn+1;K.bestx = new in t n+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.p

17、ri nt(); delete Q;delete K.w;delete K.p;4、運行結(jié)果如下圖所示：return K.bestp;void mai n()int *p;int *w;int c=0;int n=0;int i=0;char k;while(k)cout請輸入背包容量(c): c;coutvv請輸入物品的個數(shù)(n): n;p=new intn+1;w=new in t n+1;p0=0;w0=0;coutvv請輸入物品的價值(p): e ndl;for(i=1;i pi;coutvv請輸入物品的重量(w): e ndl;for(i=1;i wi;coutvv最優(yōu)解為(best

18、x): k;方案四：分枝-限界法1、分枝-限界法的基本原理與分析分枝限界發(fā)是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在 于對E-結(jié)點（expansion node的擴充方式。每個活結(jié)點有且僅有一次會變成 E- 結(jié)點。當一個結(jié)點變?yōu)镋-結(jié)點時，則生成從該結(jié)點移動一步即可到達的所有 新結(jié)點。在生成的結(jié)點中，拋棄那些不可能導(dǎo)出（最優(yōu)河行解的結(jié)點，其余結(jié)點加人活結(jié)點表，然后從表中選擇一個結(jié)點作為下一個E結(jié)點。從活結(jié)點表中取出所選擇的結(jié)點并進行擴充， 直到找到解或活動表為空，擴充才結(jié)束。2、0-1背包問題的實現(xiàn)0-1背包問題的最大收益分枝定界算法可以使用定界函數(shù)來計算活結(jié)點的 收益上限uppr

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

20、ject;class Objectfriend int Knapsack(int *,int*,i nt ,i nt ,int *);public:int operator = a.d);private:int ID;float d;單位重量價值 ;class bbnodefrie nd Kn ap;friend int Kanpsack(int *,int *,i nt ,i nt ,int *); private:bbnode * pare nt;/指向父節(jié)點 的指針bool LChild;/左兒子結(jié)點標志;class HeapNodefrie nd Kn ap;public:operat

21、or int () const retur n uprofit;void In sert(HeapNode N);void DeleteMax(He apNode N); private:int uprofit,/結(jié)點的價值上界profit;/結(jié)點所對應(yīng)的價值int weight;/結(jié)點所對應(yīng)的重量int level;/活結(jié)點在子集樹中所處的層序號bbnode * ptr; 指向活結(jié)點在 子集樹中相應(yīng)結(jié)點的指針;void HeapNode:l nsert(HeapNodeN)voidHe apNode:DeleteMax(He apNod e N)class Knapfriend int Kn

22、apsack(int *,int*,i nt ,i nt ,int *);public:int MaxK napsack();private:Heap Node *H;int MaxBo un dary(i nt i);void AddLiveNode(int up,int cp,i nt cw,bool ch,i nt level);bbnode * E;指向擴展結(jié)點的指針int c;背包容量int n;/物品總數(shù)int *w;/物品重量數(shù)組int *p;/物品價值數(shù)組int cw;/當前背包重量int cp;/當前背包價值int * bestx;/最優(yōu)解的記錄數(shù)組;計算所相應(yīng)的價值的上界i

23、nt Kn ap:MaxBo un dary(i nt i)in t cleft=c-cw;/ 剩余容量int b=cp;/價值上限/以物品單位重量價值遞減序 裝填剩余容量while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;將背包的剩余容量裝滿if(ipare nt=E;b-LChild=ch;HeapNode N;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H-l nsert(N);實施對子集樹的優(yōu)先隊列式分 支界限搜索int Kn ap:MaxK napsack()/優(yōu)先隊列式分支界限法，返回 最

24、大值，bestx返回最優(yōu)解/定義最大堆的容量為1000H=new HeapNode 1000;/為bestx分配存儲空間bestx=new int n+1;/初始化int i=1;E=0;cw=cp=0;int bestp=0;當前最優(yōu)解int up=MaxBoundary(1);價值 上界/搜索子集空間樹while(i!=n+1)/ 非葉結(jié)點/檢查當前擴展結(jié)點的左 兒子結(jié)點int wt=cw+wi;if(wtbestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+ wi,true,i+1); up=MaxBo un dary(i+1);/檢查當前擴展結(jié)點的右 兒子

25、結(jié)點if(up=bestp)AddLiveNode(up,cp,cw,false,i+ 1);/去下一個擴展結(jié)點HeapNode N;H-DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit; i=N.level;構(gòu)造當前最優(yōu)解for(i nt j=n ;j0;j-)bestxj=E-LChild;E=E-pare nt;return cp;/對數(shù)據(jù)進行預(yù)處理并完成調(diào)用MaxK napsackint Knapsack(int p,int w,int c,i nt n ,i nt bestx)/返回最大值，bestx返回最優(yōu) 解初始化

26、int W=0;/裝包物品重量int P=0; /裝包物品價值/定義依單位重量價值排序的 物品數(shù)組Object * Q=new Objectn; for(int i=1;i=n;i+)單位重量價值數(shù)組Qi-1.ID=i;Qi-1.d=(float)1.0*pi/wi;P+=pi;W+=wi;if(W=c) return P;/所有物品 裝包/依單位重量價值排序float f;for( i=0;i n;i+)for(i nt j=i;j n;j+)if(Qi.dQj.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=

27、new int n+1; 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;/調(diào)用MaxK nap sack求問題的 最優(yōu)解int bestp=K.MaxK napsack(); for(i nt j=1;j=n ;j+)bestxQj-1.ID=K.bestxj; delete Q;delete K.w;delete K.p;delete K.bestx;return bestp;4、運行結(jié)果如下圖所示：void mai n()int m,n;int i=0,j=0;in t p100,w20,x20

28、;while(1)cout0-1背包問題 遞歸法e ndl;cout請輸入背包的容量：endl;cout請輸入物品個數(shù)： e ndl;coutvv請輸入物品的重 量：endl;cout請輸入物品的價值：endl;coutvv背包的最優(yōu)解 為：endlvvKnapsack(p,w,m,n, x)e ndl;coutvv最優(yōu)解條件下選 擇的背包為:endl;for(i=1;i=n ;i+) coutxivvt;coutvve ndl;irm裁21 23 33 43 45 5531 33 43 53 55 65cont包品品品的包 3 入入入入背2 黑荊棗.1三、四種算法的比較與分析這四種算法都得到

29、了驗證，運行結(jié)果證明了算法設(shè)計是可行的， 正確的。通 過對0-1背包問題的算法設(shè)計及時間復(fù)雜度分析可以看出。無論采用貪婪法還是 動態(tài)規(guī)劃法，都是在已知約束條件下求解最大值建立數(shù)學(xué)模型算法實現(xiàn)的過程； 但算法具體實現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比較貪婪法和動態(tài)規(guī)劃 法。前者的時間復(fù)雜度低于后者，從耗費上而言優(yōu)于后者。但后者的實現(xiàn)算法可 讀性要優(yōu)于前者。動態(tài)規(guī)劃算法的基本思想是把原問題分解為一系列子問題，然后從這些子問題中求出原問題的解?；厮萜鋵嵕褪歉F舉，窮舉所有的解，找出解中最優(yōu)的值。 回溯法在包含問題的所有解的解空間樹中， 按照深度優(yōu)先的策略，從根結(jié)點出發(fā) 搜索解空間樹?；厮莘ǖ幕舅?/p>

30、路是：確定解空間，建立解空間樹，用深度優(yōu)先 搜索算法遞歸搜索解空間樹，并同時注意剪枝 ，常用的分枝一限界法有最小耗費 法，最大收益法。FIFO(先進先出)法等。0-1背包問題的分枝一限界算法可以使 用最大收益算法。該算法跟回溯法類似。但分枝限界法需要0(2)的解空間。故該算法不常用在背包問題求解?；厮莘ū确种ο藿缭谡加脙?nèi)存方面具有優(yōu)勢?；厮莘ㄕ加玫膬?nèi)存是0(解空間的最大路徑長度)，而分枝限界所占用的內(nèi)存為 0(解 空間大小)。對于一個子集空間，回溯法需要 0(n)的內(nèi)存空間，而分枝限界則需 要0(2n)的空間。雖然最大收益或最小耗費分枝限界在直覺上要好于回溯法，并 且在許多情況下可能會比回溯法

31、檢查更少的結(jié)點，但在實際應(yīng)用中，它可能會在回溯法超出允許的時間限制之前就超出了內(nèi)存的限制。通過以上對0-1背包問題的求解分析，我們可以看到各種算法設(shè)計方法有各 內(nèi)不同的特點，針對不同的問題領(lǐng)域，它們有不同的效率，對于求解0-1背包問題，各算法的時間復(fù)雜度、優(yōu)缺點以及改進方法的比較如下表所示：算法時間復(fù)雜度優(yōu)點缺點改進方法動態(tài)規(guī)劃-nO(minnc, 2 )可求得最優(yōu)決 策序列速度較慢建立動態(tài)規(guī)劃 遞歸方程回溯法O(n 2n)能夠獲得最優(yōu) 解時間復(fù)雜度較 高判斷右子樹 時，按效率密 度vi/wi對剩 余對象排序分枝-限界 法O(2n)速度較快，易 求解占用的內(nèi)存較 大，效率不咼最大收益或最 小消

32、耗分枝-限界法，F(xiàn)IFO法貪心算法O( nlogn)可以達到局部 最優(yōu)解，用時 少不能考慮到整 體最優(yōu)解，程 序可讀性低于 動態(tài)規(guī)劃對范圍廣的問 題可以產(chǎn)生接 近的最優(yōu)解#in clude#in clude#in clude#in clude#in clude#defi ne max 100/最多物品數(shù)void sort (int n,float amax,float bmax)/ 按價值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;kn;k+)ck=ak/bk;for(j=0;jn;j+)if(cjcj+1)t1=aj;aj=aj+1;aj+1=t1;t

33、2=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 為背包剩余可裝載重量sort(n,v,w);/物品按價值密度排序c1=limitw;for(i=0;ic1)break;xi=1; /xi 為1時，物品 i 在解中 c1=c1-wi;void main1()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;coutn limitw;fo

34、r(i=1;i=n;i+)xi=0;/ 物品選擇情況表初始化為 0cout 請依次輸入物品的價值： endl;for(i=1;ivi;coutendl;cout 請依次輸入物品的重量： endl;for(i=1;iwi;coutendl;knapsack (n,limitw,v,w,x);coutthe selection is:;for(i=1;i=n;i+)coutxi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutendl;cout 背包的總重量為： totalwendl; / 背包所裝載總重量 cout 背包的總價值為： totalvend

35、l; / 背包的總價值 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+)coutbestxm ;coutendl; private: int Bound(int i);void Backtrack(int i);int c;/ 背包容量int n; / 物品數(shù)int *w;/ 物品重量數(shù)組int *p;/ 物品價值數(shù)組int cw;/ 當前重量int cp;/ 當前價值int bestp;/ 當前最優(yōu)值int *b

36、estx;/ 當前最優(yōu)解int *x;/ 當前解;int Knap:Bound(int i)/計算上界int cleft=c-cw;/ 剩余容量int b=cp; /以物品單位重量價值遞減序裝入物品 while(i=n&wi=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);class Objectfriend int Knapsack(int p,int w,int c,

37、int n); public:int operator=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; if(W=c) return P;/ 裝入所有物品 /依物品單位重量排序 float f;for( i=0;in;i+) for(int j=i

38、;jn;j+)if(Qi.dQj.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.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1);K.print(); delete Q; delete K.w; delete K.p; r

39、eturn K.bestp; void main2() int *p; int *w;int c=0; int n=0; int i=0; char k; while(k) cout 請輸入背包容量 (c)： c;cout 請輸入物品的個數(shù) (n)： n;p=new intn+1; w=new intn+1;p0=0; w0=0;cout 請輸入物品的價值 (p)： endl; for(i=1;ipi;cout 請輸入物品的重量 (w) ： endl; for(i=1;iwi; cout 最優(yōu)解為 (bestx)： endl; cout 最優(yōu)值為 (bestp)： endl; coutKnap

40、sack(p,w,c,n)endl;couts 重新開始 endl; coutq 退出 k;class Knap;class Object;class Objectfriend int Knapsack(int *,int *,int ,int ,int *); public:int operator = a.d);private: int ID; float d;/ 單位重量價值;class bbnodefriend Knap; friend int Kanpsack(int *,int *,int ,int ,int *);private: bbnode * parent;/ 指向父節(jié)點的

41、指針 bool LChild;/左兒子結(jié)點標志;class HeapNode friend Knap;public: operator int () const return uprofit; void Insert(HeapNode N); void DeleteMax(HeapNode N);private:int uprofit, /結(jié)點的價值上界 profit;/結(jié)點所對應(yīng)的價值int weight; /結(jié)點所對應(yīng)的重量 int level;/ 活結(jié)點在子集樹中所處的層序號bbnode * ptr; / 指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針 ;void HeapNode:Insert(HeapNode N)void HeapNode:DeleteMax(HeapNode N)class Knapfriend int Knapsack(int *,int *,int ,int ,int *); public:int MaxKnapsack();private:HeapNode *H;in