1、蘭州交通大學數理與軟件工程學院題 目0-1背包問題算法實現院系數理院專業班級信計09學生姓名雷雪艷學號200905130指導教師二0二年六月五日、問題描述：1、 0 1背包問題：給定n種物品和一個背包，背包最大容量為M，物 品i的重量是Wi,其價值是平Pi，問應當如何選擇裝入背包的物品，似的裝 入背包的物品的總價值最大？背包問題的數學描述如下：2、要求找到一個n元向量(x1，x2-xn)，在滿足約束條件：XiWiM0 x 1maxXi Pi0 Xi 1情況下，使得目標函數，其中，1 i n ；M>0 ；wi>0 ； pi>0。滿足約束條件的任何向量都是一個可行解，而使得目標函

2、數 達到最大的那個可行解則為最優解1。給定n種物品和1個背包。物品i的重量是wi，其價值為pi，背包 的容量為M。問應如何裝入背包中的物品，使得裝人背包中物品的總價值 最大？在選擇裝人背包的物品時，對每種物品i只有兩種選擇，即裝入背包、 不裝入背包。不能將物品i裝人背包多次，也不能只裝入部分的物品i。該 問題稱為0-1背包問題。0-1背包問題的符號化表示是，給定M>0 ，w i >0， pi >0 , 1 in， 要求找到一個n元0-1向量向量(x1，x2 -Xn)，X i =0 或1 , 1 i n,使 得xw M，而且X Pi達到最大2】、解決方案:方案一：貪心算法1、貪

3、心算法的基本原理與分析貪心算法總是作出在當前看來是最好的選擇，即貪心算法并不從整體最 優解上加以考慮，它所作出的選擇只是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣的許多問題它能產 生整體最優解。在一些情況下，即使貪心算法不能得到整體最優解， 但其最 終結果卻是最優解的很好近似解。貪心算法求解的問題一般具有兩個重要性質：貪心選擇性質和最優子結構性質。所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部 最優解的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素， 也是貪心算法與動態規劃算法的主要區別。當一個問題的最優解包含其子問題的最優解時，稱

4、此問題具有最優子結構性質。問題的最優子結構性質是該 問題可用動態規劃算法或貪心算法求解的關鍵特征。2、0-1背包問題的實現對于0-1背包問題，設A是能裝入容量為c的背包的具有最大價值的物品集合，則Aj=A-j是n-1個物品1,2,j-1,j+1,n可裝入容量為c-wj的 背包的具有最大價值的物品集合。用貪心算法求解0-1背包問題的步驟是，首先計算每種物品單位重量的 價值vi/wi ;然后，將物品進行排序，依貪心選擇策略，將盡可能多的單位 重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總量未超過C,則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直進行下去，直到

5、背包裝滿為止。3、算法設計如下：#in clude<iostream.h>#defi nemax100/最多物品數void sort (intn floatamax,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(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 kn apsack(i ntn floatlimitw,fl

6、oatvmax,floatwmax,i nt xmax)floatc1;c1為背包剩余可裝載重量int i;sort (n ,v,w);/物品按價值密度排序c1=limitw;for(i=0;i <n ;i+)if(wi>c1)break;xi=1;/xi為1時，物品i在解中c1=c1-wi;void mai n()int n ,i,xmax;floatvmax,wmax,totalv=0,totalw=0,limitw;cout«"請輸入 n 和 limitw:"cin>>n >>limitw;for(i=1;i<=n

7、;i+)xi=0;/物品選擇情況表初始化為0 coutvv"請依次輸入物品的價 值："<<endl;for(i=1;i<=n ;i+)cin> >vi;cout«e ndl;coutvv"請依次輸入物品的重量："<<endl;for(i=1;i<=n ;i+)cin> >wi;coutvve ndl;kn apsack (n ,limitw,v,w,x);4、貪心算法運行結果如下圖所示: cout<<"the selectio n is:"for(i=1

8、;i<=n ;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutvve ndl;coutvv"背包的總重量為："vvtotalwvvendl; / 背包所裝載總重量coutvv"背包的總價值為： "vvtotalvvvendl; / 背包的總 價值請低抄:愉入物品的車量149the 總左丄ection Is：11U 背就的總車凰為，76 背包的總價值為 65 PreHM dii V le y Lu cun t 丄方案二：動態規劃算法1、動態規劃的基本原理與分析動態規劃算法

9、的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。但是經分解得到的子問題往往不是互相獨立的。不同子問題的數目常常只有多項式量級。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產生最佳的結果舍棄其余。前一子問題為后面子問題提供信息，而減少計算量，最后一個子問題的解即為問題解。采用此方法求解0-1背包問題的主要步驟如下： 分析最優解的結構：最有子結構性質； 建立遞歸方程； 計算最優

10、值； 構造最優解。2、0-1背包問題的實現最優子結構性質0-1背包問題具有最優子結構性質。設(y1 , y2-yn)是所給0-1背包問 題的一個最優解，則(y2 , y3yn)是下面相應子問題的一個最優解：nmax VkXkk inWkXkjk iXk 0,1, i k n因若不然，設(z2 , z3zn)是上述問題的一個最優解，而(y2 , y3n)不是nnvi yiw1y1wi z它的最優解，由此可見i 2，且2C。因此nnvlylVi ZiViyii 2i 1nwlylwi zi 2 c這說明(y1 , z2-zn)是所給0-1背包問題的一個更優解，從而(y1 , y2yn)不是所給0-

11、1背包問題的最優解。此為矛盾1遞歸關系設所給0-1背包問題的子問題nmaxVkXkk inWkXkjk iXk0,1, i k n的最優值為m(i,j)，即m(i,j)是背包容量為j,可選擇物品為i, i+1 , n時0-1背包問題的最優值。由0-1背包問題的最優子結構性質，可以建立計算m(i,j)的遞歸式如下：maxm(i 1), j),m(i 1, j wi)m(i,j)vnj wn m(n,j).0 j wn3、算法設計如下：#in clude<iostream>#i ncludevioma nip>using n amespace std;const int MAX=

12、1000;intwMAX,vMAX,bestMAX;int VMAXMAX; / 最大價值矩陣int W,n;/W為背包的最大載重量，n為物品的數量/求最大值函數int max(i nt x,i nt y)retur n x >= y?x:y;/求最小值函數vi, j wim(i 1 j),0 j wjretur 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 <= W ; j+)V nj=v n;for(i nt i=n

13、-1;i > 1 ; i-)Max=mi n(wi-1,W);for( j=1; j <= Max ; j+)Vij=Vi+1j;for( j=wi; j <= W; j+)Vij=max(Vi+1j,Vi+1int min (i nt x,i nt y)j-wi+vi);V1W=V2W;/ 先假設第一個物品不放入if(W > w1)V1W=max(V1W,V2W-w1+v1);/生成向量數組，決定某一個物 品是否應該放入背包void Traceback()for(i nt i=1; i < n ; i+)/比較矩陣兩鄰兩行(除最后一 行)，背包容量為W的最優值.

14、if(ViW = Vi+1W)/如果當前行的最優值與下一 行的最優值相等，則表明該物品 不能放入。else/否則可以放入besti=1;W-=wi;bestn=(VnW )?1:0;void mai n()cout«"輸入商品數量 n和背包容量W:"cin»n>>W;coutvv"輸入每件商品的重量 w:"<<endl;for(int i=1;i<=n;i+)ci n> >wi;memset(V,0,sizeof(V);coutvv"輸入每件商品的價值 v:"<<

15、;endl;besti=0;for( i=1;i<=n ;i+)cin> >vi;Knaspack();構造矩陣Traceback(); /求出解的向量數組int totalW=0;int totalV=0;/顯示可以放入的物品cout«"所選擇的商品如下:"<<e ndl;coutvv"序號i:重量w:價格 v:"<<e ndl;for(i=1; i <= n ; i+)if(besti = 1)totalW+=wi;4、計算復雜性分析totalV+=vi;cout<<setiosf

16、lags(ios:left) <<setw(5)<<i<<""<<wi<<""<<vi<<e ndl;cout«"放入的物品重量總和是:"vvtotalWvv" 價值最 優解是:"<<V1W<<" "vvtotaIVvve ndl;利用動態規劃求解0-1背包問題的復雜度為0(minnc,2n。動態規劃主 要是求解最優決策序列，當最優決策序列中包含最優決策子序列時，可建立 動態規劃

17、遞歸方程，它可以幫助高效地解決問題8。5、動態規劃運行結果如下圖所示：81 C;Progranri F lesMiVisual Studi-oMyProjectscvDcbugexew車俞入 商品審n和背包容號VJ： 3N7 嗇人営祥商翥的重量32J 6U 56輸人每件商品的價值*序號1 5 B W :彳介榕U :1 23342 6Q65放入的槻啟重量總和是，叮價值最優解是詛站Press -am key to cont ±nu.eH方案三：回溯法1、回溯法的基本原理與分析回溯是一種系統地搜索問題解答的方法。為了實現回溯，首先需要為問題 定義一個解空間，這個解空間必須至少包含問題的一個

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

19、搜索問題解答的方法。為了實現回溯，首先需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解（可能是最優的）。一旦定義了解空間的組織方要選擇一個對象的子集，將它們裝人背包， 以便獲得的收益最大，則解空間應組織成子集樹的形狀。首先形成一個遞歸算法，去找到可獲得的最大收益。然后，對該算法加以改進，形成代碼。改進后的代碼可找到獲得最大收益時包含在背包中的對象的集合。左子樹表示一個可行的結點，無論何時都要移動到它，當右子樹可能含 有比當前最優解還優的解時，移動到它。一種決定是否要移動到右子樹的簡 單方法是r為還未遍歷的對象的收益之和，將 r加到cp （當前節點所獲收益） 之上，若（葉cp） be

20、stp（目前最優解的收益），則不需搜索右子樹。一種更 有效的方法是按收益密度vi/wi對剩余對象排序，將對象按密度遞減的順序 去填充背包的剩余容量，當遇到第一個不能全部放人背包的對象時，就使用它的一部分。3、算法設計如下：#in clude<iostream>using n amespace std;class Knapfriend int Kn apsack(i nt p,i ntw,i nt c,i nt n );public:void prin t()cout«e ndl;private:int Boun d(i nt i);void Backtrack©

21、 nt i);int c;/背包容量int n; /物品數int *w;/物品重量數組int *p;/物品價值數組int cw;/當前重量cout<<bestxmvv""int cp;/當前價值int bestp;/當前最優值int *bestx;/當前最優解int *x;/當前解；int Kn ap:Bo un d(i nt i)/計算上界in t cleft=c-cw;剩余容量int b=cp;/以物品單位重量價值遞減序 裝入物品while(i<=n&&wiv=cleft)cleft-=wi;b+=pi;i+;/裝滿背包if(i<

22、=n)b+=pi/wi*cleft;return b;void Kn ap:Backtrack(i nt i)if(i> n)if(bestp<cp)for(i nt j=1;j<=n ;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) /搜索左子樹xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw_=wi;cp-=pi;if(Bou nd(i+1)>bestp)搜索右子樹xi=O;Backtrack(i+1);class Objectfrie nd int Kn apsack(i nt p,i ntw,i

23、nt c,i nt n);public:intoperator<=(Objecta)c onstreturn (d>=a.d);private:int ID;float d;intKn apsack(i ntp,i nt/ 為 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

24、<n ;i+)for(i nt j=i;j< n;j+)if(Qi.d<Qj.d)w,i nt c,i nt n)f=Qi.d;/回溯搜索Qi.d=Qj.d;K.Backtrack(1);Qj.d=f;K.pri nt();delete Q;delete K.w;Knap K;delete K.p;K.p = new intn+1;return K.bestp;K.w = new in t n+1;K.x = new intn+1;void mai n()K.bestx = new in t n+1;K.xO=O;int *p;K.bestxO=O;int *w;for( i

25、=1;i<=n ;i+)int c=0;int n=0;K.pi=pQi-1.ID;int i=0;K.wi=wQi-1.ID;char k;while(k)K.cp=0;K.cw=0;cout«"請輸入背包容量（c）:K.c=c;"<<e ndl;K. n=n;cin> >c;K.bestp=0;coutvv"請輸入物品的個數(n): "<<endl;cin»n;p=new in t n+1;w=new in t n+1;p0=0；w0=0;coutvv"請輸入物品的價值(p):

26、"<<endl;for(i=1;i<=n ;i+)cin> >pi;cout«"請輸入物品的重量(w): "<<endl;for(i=1;i<=n ;i+)4、運行結果如下圖所示：cin> >wi;cout«" 最優解為(bestx):"<<e ndl;cout«" 最優值為(bestp):"<<e ndl;cout«K napsack(p,w,c ,n)<<en dl;cout<&l

27、t;"s 重新開始"<<e ndl;cout«"q退出"<<endl;cin> >k;請輸入背包容量J兒90蘋輸入物en的個數<">< 量蹩物品的價值 3, 請輸入物品的重量78 5曇如舞再5*七9 I 駆/憂值 Ki 5*七卩& 1二】重拈幵貽方案四：分枝-限界法1、分枝-限界法的基本原理與分析分枝限界發是另一種系統地搜索解空間的方法，它與回溯法的主要區別在 于對E-結點（expansion node）的擴充方式。每個活結點有且僅有一次會變成 E-結點。當一個結點變為E-

28、結點時，則生成從該結點移動一步即可到達的所 有新結點。在生成的結點中，拋棄那些不可能導出（最優河行解的結點，其余結點加人活結點表，然后從表中選擇一個結點作為下一個E結點。從活結點表中取出所選擇的結點并進行擴充，直到找到解或活動表為空，擴充才結 束。2、0-1背包問題的實現0-1背包問題的最大收益分枝定界算法可以使用定界函數來計算活結點 的收益上限upprofit，使得以活結點為根的子樹中的任一結點的收益值都不 可能超過upprofit ，活結點的最大堆使用upprofit作為關鍵值域。在子集樹 中執行最大收益分枝定界搜索的函數首先初始化活結點的最大堆，并使用一 個數組bestx來記錄最優解。由

29、于需要不斷地利用收益密度來排序，物品的 索引值會隨之變化，因此必須將函數所生成的結果映射回初始時的物品索引。 函數中的循環首先檢驗E-結點左孩子的可行性，如它是可行的，則將它加入 子集樹及活結點隊列（即最大堆），僅當結點右子樹的定界值指明可能找到一 個最優解時才將右孩子加入子集樹和隊列中。3、算法設計：#i nclude <iostream.h>class Kn ap;class Object;class Objectfrie nd int Kn apsack(i nt *,i nt*,i nt ,i nt ,int *);public:int operator v=(Object

30、a)c onstreturn (d >= a.d);private:int ID;float d;單位重量價值;class bbnodefrie nd Kn ap;frie nd int Kan psack(i nt *,i nt*,i nt ,i nt ,int *);private:bbnode * pare nt;指向父節點的指針bool LChild; / 左兒子結 點標志;class HeapNodefrie nd Kn ap;public:operator int () const retur n uprofit;void In sert(HeapNode N);voidDe

31、leteMax(He apNode N);private:int uprofit,/結點的價值上界profit; /結點所對應的價值int weight; /結點所對應的重量int level; /活結點在子集樹中所處的層序號bbnode * ptr; / 指向活結點在子集樹中相應結點的指針;voidHeapNode:l nsert(HeapNode N)voidHe apNode:DeleteMax(HeapNode N)class Knapfrie nd int Kn apsack(i nt *,i nt*,i nt ,i nt ,int *);public:int MaxK napsac

32、k();private:Heap Node *H;int MaxBo un dary(i nt i);voidAddLiveNode(i ntup,i nt cp,i nt cw,bool ch,i nt level);bbnode * E; / 指向擴 展結點的指針int c;/背包容量int n;/物品總數int *w;/物品重量數組int *p;/物品價值數組int cw;/當前背包重量int cp;/當前背包價值int * bestx;/最優解的記錄數組;/計算所相應的價值的上界int Kn ap:MaxBo un dary(i nt i)int cleft=c-cw; / 剩余容量i

33、nt b=cp;/ 價值上限/以物品單位重量價值遞減序裝填剩余容量while(i<=n&&wi<=cleft)cleft-=wi;b+=pi;i+；/將背包的剩余容量裝滿if(i<=n)b+=pi/wi*cleft;return b;/將一個新的活結點插入到子集樹和優先隊列中void Kn ap:AddLiveNode(i ntup,i nt cp,i nt cw,bool ch,i ntlev)/將一個新的活結點插入到子集樹和最大堆H中bbnode * b=new bbno de;b->pare nt=E;b->LChild=ch;HeapNod

34、e N;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H->I nsert(N);/實施對子集樹的優先隊列式分支界限搜索int Kn ap:MaxK napsack()/優先隊列式分支界限法，返回最大值，bestx返回最優解/定義最大堆的容量為1000H=new HeapNode 1000;/為bestx分配存儲空間bestx=new int n+1;/初始化int i=1;E=0;cw=cp=0;int bestp=0; / 當前最優解int up=MaxBoundary(1);價值上界/搜索子集空間樹while(i!

35、=n+1)非葉結點/檢查當前擴展結點的左 兒子結點int wt=cw+wi;if(wt<=c)if(cp+pi>bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=MaxBo un dary(i+1);/檢查當前擴展結點的右兒子結點if(up>=bestp)AddLiveNode(up,cp,cw,false,i+1);/去下一個擴展結點HeapNode N;H->DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofit; i=N.level;/構造

36、當前最優解for(i nt j=n ;j>O;j-)bestxj=E->LChild;E=E->pare nt;return cp;/對數據進行預處理并完成調用 MaxK nap sackintKn apsack(i ntp,i ntfloat f;for( i=0;i< n;i+)for(i nt j=i;j< n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;/創建類Knap的數據成員Knap K;K.p=new int n+1;K.w=new int n+1; for(i=1;i<=n ;i+)K.pi=pQi-

37、1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;w,i nt c,i nt n ,i nt bestx)/返回最大值，bestx返回最優解/初始化int W=0;/裝包物品重量int P=0;/裝包物品價值/定義依單位重量價值排序的物品數組Object * Q=new Object n;for(int i=1;i<=n;i+)/單位重量價值數組Qi-1.ID=i;Qi-1.d=(float)1.0*pi/wiJP+=pi；W+=wi;if(W<=c) return P;/ 所有物品裝包/依單位重量價值排序K.c=c;K. n=n;/調用MaxKnapsack求問題

38、的最優解intbestp=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;void mai n()int m,n;int i=0,j=0;in t p100,w20,x20;while(1)cout<<"0-1 背包問題一遞歸法"<<endl;cout«"請輸入背包的容量："<<endl;coutvv"請

39、輸入物品個數： "<<e ndl;coutvv"請輸入物品的重 量："<<endl;coutvv"請輸入物品的 價值："<<endl;coutvv"背包的最優 解為："vvendlvvKnapsack(p,w, m,n, x)vve ndl;coutvv"最優解條件下選擇的背包為:"vvendl;for(i=1;iv=n ;i+)coutvvxivv"t" coutvve ndl;4、運行結果如下圖所示:intip31 23們呻3船$5 n 31 4

40、35占殆to14帰 邑品.JLrnn半 f X 背翱夠直孑措爲 A'入入入背上價S 釉錨歸棗.，優CS三、四種算法的比較與分析這四種算法都得到了驗證，運行結果證明了算法設計是可行的，正確的。通過對0-1背包問題的算法設計及時間復雜度分析可以看出。無論采用貪婪法還 是動態規劃法，都是在已知約束條件下求解最大值建立數學模型算法實現的過 程；但算法具體實現和數據結構的建立要用到遞歸和棧操作。比較貪婪法和動態規劃法。前者的時間復雜度低于后者，從耗費上而言優于后者。但后者的實現算 法可讀性要優于前者。動態規劃算法的基本思想是把原問題分解為一系列子問題，然后從這些子問題中求出原問題的解。回溯其實就

41、是窮舉，窮舉所有的解，找出解中最優的值。 回溯法在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。回溯法的基本思路是：確定解空間，建立解空間樹，用深度優先 搜索算法遞歸搜索解空間樹，并同時注意剪枝，常用的分枝一限界法有最小耗費法，最大收益法。FIFO（先進先出）法等。0-1背包問題的分枝一限界算法可以使 用最大收益算法。該算法跟回溯法類似。但分枝限界法需要0（2）的解空間。故該算法不常用在背包問題求解。回溯法比分枝限界在占用內存方面具有優勢。回溯法占用的內存是0（解空間的最大路徑長度），而分枝限界所占用的內存為0（解 空間大小）。對于一個子集空間，回溯法需要 0（n

42、）的內存空間，而分枝限界則需要0(2n)的空間。雖然最大收益或最小耗費分枝限界在直覺上要好于回溯法，并且在許多情況下可能會比回溯法檢查更少的結點，但在實際應用中，它可能會在回溯法超出允許的時間限制之前就超出了內存的限制。通過以上對0-1背包問題的求解分析，我們可以看到各種算法設計方法有各內不同的特點，針對不同的問題領域，它們有不同的效率，對于求解0-1背包問題，各算法的時間復雜度、優缺點以及改進方法的比較如下表所示：算法時間復雜度優點缺點改進方法動態規劃cnO(minnc, 2 )可求得最優決策丿予列速度較慢建立動態規劃遞歸方程回溯法cnO(n 2)能夠獲得最優解時間復雜度較高判斷右子樹 時，

43、按效率密度vi/wi對剩余對象排序分枝-限界法O(2)速度較快，易求解占用的內存較大，效率不咼最大收益或最 小消耗分枝-限界法，FIFO法貪心算法O(nlogn )可以達到局部最優解，用時少不能考慮到整 體最優解，程 序可讀性低于 動態規劃對范圍廣的問題可以產生接近的最優解#in clude<iostream.h>#in clude<iostream>#in clude<stdio.h>#in clude<c oni o.h>#in clude<stdlib.h>#define max 100/最多物品數void sort (int

44、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(cj<cj+1)t1=a j;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為背包剩余可裝載重量sort( n,v,w);/物品

45、按價值密度排序c1=limitw;for(i=0;i< n;i+)if(wi>c1)break;xi=1;xi為1時，物品i在解中c1=c1-wi;void ma in 1()int n ,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;cout<<" 請輸入n和總重量："；cin»n >>limitw;for(i=1;i<=n ;i+)xi=0;/cout<<" 請依次輸入物品的價值："<<e ndl;for(i=1;i<=

46、n ;i+)cin> >vi;cout<<e ndl;cout<<" 請依次輸入物品的重量："<<e ndl;for(i=1;i<=n ;i+)cin> >wi;cout<<e ndl;kn apsack (n ,limitw,v,w,x);cout<<"the select ion is:"for(i=1;i<=n ;i+)cout<<xi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;cout<<

47、;e ndl;背包所裝載總重量背包的總價值cout<<"背包的總重量為："<<totalw<<e ndl; /cout<<"背包的總價值為："<<totalv<<e ndl; / using n amespace std;class Knapfriend int Kn apsack(i nt p,i nt w,i nt c,i nt n );public:void prin t()for(i nt m=1;m <=n; m+)cout<<bestxm<<

48、""cout<<e ndl;private:int Boun d(i nt i);void Backtrack(i nt i);int c;/背包容量int n; /物品數int *w;物品重量數組int *p;物品價值數組int cw; 當前重量in t cp;/當前價值int bestp;/當前最優值int *bestx;當前最優解int *x;當前解；int Kn ap:Bo un d(i nt i)/計算上界in t cleft=c-cw; 剩余容量int b=cp;/以物品單位重量價值遞減序裝入物品 while(i<=n&&wi&

49、lt;=cleft) cleft-=wi;b+=pi;i+;/裝滿背包 if(i<=n)b+=pi/wi*cleft;return b;void Kn ap:Backtrack(i nt i)if(i> n)if(bestp<cp)for(i nt j=1;j<=n ;j+)bestxj=xj;bestp=cp;return;if(cw+wi<=c) /搜索左子樹xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;if(Bou nd(i+1)>bestp)搜索右子樹xi=O;Backtrack(i+1);class

50、 Objectfriend int Kn apsack(i nt p,i nt w,i nt c,i nt n);public:int operator<=(Object a)c onstreturn (d>=a.d);private:int ID;float d;int Kn apsack(i nt p,i nt w,i nt c,i nt n)/ 為 Knap:Backtrack 初始化int W=0;int P=0;in t i=1;Object *Q=new Objectn;for(i nt i=1;i<=n ;i+)Qi-1D=i;Qi-1.d=1.0*pi/wi;

51、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.d<Q j.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.xO=O;K.bestxO=O;for( i=1;i<=n ;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0

52、;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K.pri nt();delete Q;delete K.w;delete K.p;return K.bestp;void mai n2()int *p;int *w;int c=0;int n=0;int i=0;char k;while(k)cout<<" 請輸入背包容量(c): "<<endl;cin> >c;cout<<" 請輸入物品的個數(n) : "<<endl;cin»n;

53、p=new intn +1;w=new intn+1;p0=0;w0=0;cout<<" 請輸入物品的價值(p) : "<<endl;for(i=1;i<=n ;i+)cin> >pi;cout<<" 請輸入物品的重量(w) : "<<endl;for(i=1;i<=n ;i+)cin> >wi;cout<<"最優解為(bestx) : "<<endl;cout<<"最優值為(bestp) : "<<endl;cout<<K napsack(p,w,c, n)<<en dl;cout<<"s 重新開始"<<endl;cout<<"q退出"<<