算法分析與設(shè)計(jì)課程的設(shè)計(jì)論文

1、 信息技術(shù)學(xué)院算法設(shè)計(jì)與分析課程考查論文題 目0-1背包問(wèn)題的算法設(shè)計(jì)策略對(duì)比與分析專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) 2006級(jí)軟件方向 學(xué) 號(hào) 061124015 姓 名 劉翠蘭 任 課 教 師 宋振方 完 成 日 期 2008年12月31日 0-1背包問(wèn)題的算法設(shè)計(jì)策略對(duì)比與分析0 引言對(duì)于計(jì)算機(jī)科學(xué)來(lái)說(shuō)，算法的概念是至關(guān)重要的，例如，在一個(gè)大型軟件系統(tǒng)的開(kāi)發(fā)中，設(shè)計(jì)出有效的算法將起決定性的作用。算法是解決問(wèn)題的一種方法或一個(gè)過(guò)程。程序是算法用某種設(shè)計(jì)語(yǔ)言具體實(shí)現(xiàn)描。計(jì)算機(jī)的普及極大的改變了人們的生活。目前，各行業(yè)、各領(lǐng)域都廣泛采用了計(jì)算機(jī)信息技術(shù)，并由此產(chǎn)生出開(kāi)發(fā)各種應(yīng)用軟件的需求。為了

2、以最小的成本、最快的速度、最好的質(zhì)量開(kāi)發(fā)出適合各種應(yīng)用需求的軟件，必須遵循軟件工程的原則。設(shè)計(jì)一個(gè)高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的素算法，這正是計(jì)算機(jī)科學(xué)領(lǐng)域數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)所研究的主要內(nèi)容。1 算法復(fù)雜性分析的方法介紹算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)

3、表示，則有： T=T(N,I)和S=S(N,I) 。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中最壞情況下的時(shí)間復(fù)雜性：最好情況下的時(shí)間復(fù)雜性：平均情況下的時(shí)間復(fù)雜性：其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N, I*)達(dá)到Tmax(N)的合法輸入； 是中使T(N, )達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、o 設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)

4、=O(g(N)。即f(N)的階不高于g(N)的階。 根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則： (1)O(f)+O(g)=O(max(f,g)； (2)O(f)+O(g)=O(f+g)； (3)O(f)O(g)=O(fg)； (4)如果g(N)=O(f(N)，則O(f)+O(g)=O(f)； (5)O(Cf(N)=O(f(N)，其中C是一個(gè)正的常數(shù)； (6)f=O(f)。 的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=(g(N)。即f(N)的階不低于g(N)的階。 的定義：定義f(N)= (

5、g(N)當(dāng)且僅當(dāng)f(N)=O(g(N)且f(N)= (g(N)。此時(shí)稱f(N)與g(N)同階。o的定義：對(duì)于任意給定的0，都存在正整數(shù)N0，使得當(dāng)NN0時(shí)有f(N)/Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時(shí)的階比g(N)低，記為f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。 2 常見(jiàn)的算法分析設(shè)計(jì)策略介紹2.1 遞歸與分治策略分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。

6、將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。由于分治法產(chǎn)生的子問(wèn)題往往是原來(lái)問(wèn)題的較小規(guī)模，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易求出其解。由此自然引出遞歸算法。分治與遞歸像是一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效的算法。2.2 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。如果能

7、夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。動(dòng)態(tài)規(guī)劃的一般步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2.3 貪心算法 顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題，用貪心算法更簡(jiǎn)單、更直接且解題效率更高。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路

8、經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。 2.4 回溯法有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題?；厮莘ㄔ趩?wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。問(wèn)題的解向量：回溯法

9、希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。2.5 分支限界法分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(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é)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這

10、個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法： 隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 最大優(yōu)先隊(duì)列：使用最大堆，體現(xiàn)最大效益優(yōu)先 最小優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用優(yōu)先 3 結(jié)合0-1背包問(wèn)題詳述動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法解決問(wèn)題的過(guò)程 0-1背包問(wèn)題：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量是c。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中的物品

11、總價(jià)值最大。在選擇裝入背包的物品時(shí)，對(duì)每種物品i只能有兩種選擇，裝入包或者不裝入。不能物品i裝入包多次，也不能之裝入部分的物品i。 3.1 動(dòng)態(tài)規(guī)劃算法問(wèn)題描述此問(wèn)題的形式化描述是，給定c0,Wi0,Vi0，1in，要求找出一個(gè)n元0-1向量（x1，x2，xn），Xi0,1,1in，使得，而且達(dá)到最大。因此0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題： 算法描述： 設(shè)所給0-1背包問(wèn)題的子問(wèn)題 max(Vk * Xk) k=i.n ；max(Vk * Xk)= j (k=i.n )；Xk 0，1，i=k=n ；的最優(yōu)值為m（i，j）是背包容量為j，可選擇物品為i，i+1，,n時(shí)0-1背包問(wèn)題的最優(yōu)值

12、。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以建立計(jì)算m(i,j)的遞歸式如下：m(i，j) = maxm(i+1，j)，m(i+1，j-wi)+ Vi j = wim(i，j) = m(i+1,j) 0 = j = wnm(n,j) = 0 0 = j wn 程序：#include#define Max 101int mMaxMax,wMax,vMax,xMax;void Knapsack(int c,int n) int jMax=min(wn-1,c); for(int j=0;j=jMax;j+)mnj=0; for(int j=wn;j1;i-) jMax=min(wi-1,c); f

13、or(int j=0;jjMax;j+)mij=mi+1j; for(int j=wi;j=w1)m1c=max(m1c,m2c-w1+v1);void Traceback(int c,int n) for(int i=0;in;i+) if(mic=mi+1c)xi=0; else xi=1;c-=wi; xn=(mnc)?1:0;int main()int n,i,c;while(scanf(%d,&n)&n)scanf(%d,&c);for(i=1;i=n;i+)scanf(%d%d,&vi,&wi);Knapsack(c,n);Traceback(c,n);for(i=1;i=n;i+

14、)printf(%d ,xi);printf(n);return 0;3.2貪心算法問(wèn)題描述： 假定有n個(gè)物體和一個(gè)背包，物體i 有質(zhì)量wi，價(jià)值為pi，而背包的載荷能力為M。若將物體i的一部分xi（1=i=n,0=xi=1)裝入背包中，則有價(jià)值pi*xi。在約束條件（w1*x1+w2*x2+wn*xn)=M下使目標(biāo)(p1*x1+p2*x2+pn*xn)達(dá)到極大，此處0=xi0,1=i=n.這個(gè)問(wèn)題稱為背包問(wèn)題（Knapsack problem）。 算法描述 首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，

15、背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 程序代碼： #include struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品該放的數(shù)量 int flag; /物品編號(hào) ; /物品信息結(jié)構(gòu)體 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(

16、goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/當(dāng)該物品重量大與剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/確定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/該物品所要放的量 for(j=2;j=n;j+) /*按物品編號(hào)做降序排列*/ goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goo

17、dsi; i-; goodsi+1=goods0; / cout最優(yōu)解為:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() cout|-運(yùn)用貪心法解背包問(wèn)題-|endl; cout|-power by zhanjiantao(028054115)-|endl; cout|-|endl; int j; int n; float M; goodinfo *goods;/定義一個(gè)指針 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int

18、 i; for(i=1;i=n;i+) goodsi.flag=i; cout請(qǐng)輸入第igoodsi.w; cout請(qǐng)輸入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; 3.3回溯算法問(wèn)題描述：對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4，c=7，p=9,10,7,4,w=3,5,2,1.這4個(gè)物品的單位重量?jī)r(jià)值分別為3,2,3,5,4.以物品為單

19、位價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝入0.2的物品2.由此可得到一個(gè)解為x=1,0,2,1,1,其相應(yīng)的價(jià)值為22.盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)22.算法描述：0-l背包問(wèn)題是子集選取問(wèn)題。一般情況下，0-1背包問(wèn)題是NP難題。0-1背包問(wèn)題的解空間可用子集樹(shù)表示。解0-1背包問(wèn)題的回溯法與裝載問(wèn)題的回溯法十分類似。在搜索解空間樹(shù)時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹(shù)。當(dāng)右子樹(shù)有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹(shù)搜索。否則將右子樹(shù)剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和

20、；cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+rbestp時(shí)，可剪去右子樹(shù)。計(jì)算右子樹(shù)中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹(shù)中解的上界。程序：#includeusing 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);

21、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=cleft) cleft-=wi; b+=pi; i+; /裝滿背包 if(in) if(bestpcp) for(in

22、t j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子樹(shù) xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,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 Objec

23、tn; 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; 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;

24、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; char k; cout0-1背包問(wèn)題回溯法 endl; cout by zbqplayer endl; while(k) cout請(qǐng)輸入背包容量(c)：c; cout請(qǐng)輸入物

25、品的個(gè)數(shù)(n)：n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout請(qǐng)輸入物品的價(jià)值(p)：endl; for(i=1;ipi; cout請(qǐng)輸入物品的重量(w)：endl; for(i=1;iwi; cout最優(yōu)解為(bestx)：endl; cout最優(yōu)值為(bestp)：endl; coutKnapsack(p,w,c,n)endl; couts 重新開(kāi)始endl; coutq 退出k; 3.4分支限界問(wèn)題描述：已知有N個(gè)物品和一個(gè)可以容納M重量的背包，每種物品I的重量為WEIGHT，一個(gè)只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的

26、總效益最大。對(duì)物品的選取與否構(gòu)成一棵解樹(shù)，左子樹(shù)表示不裝入，右表示裝入，通過(guò)檢索問(wèn)題的解樹(shù)得出最優(yōu)解，并用結(jié)點(diǎn)上界殺死不符合要求的結(jié)點(diǎn)。算法描述：首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹(shù)和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹(shù)和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問(wèn)題的最優(yōu)值。程序：#inclu

27、de struct good int weight; int benefit; int flag;/是否可以裝入標(biāo)記;int number=0;/物品數(shù)量int upbound=0;int curp=0, curw=0;/當(dāng)前效益值與重量int maxweight=0;good *bag=NULL;void Init_good() bag=new good number; for(int i=0; inumber; i+) cout請(qǐng)輸入第件i+1bagi.weight; cout請(qǐng)輸入第件i+1bagi.benefit; bagi.flag=0;/初始標(biāo)志為不裝入背包 coutendl; i

28、nt getbound(int num, int *bound_u)/返回本結(jié)點(diǎn)的c限界和u限界 for(int w=curw, p=curp; numnumber & (w+bagnum.weight)=maxweight; num+) w=w+bagnum.weight; p=w+bagnum.benefit; *bound_u=p+bagnum.benefit; return ( p+bagnum.benefit*(maxweight-w)/bagnum.weight) );void LCbag() int bound_u=0, bound_c=0;/當(dāng)前結(jié)點(diǎn)的c限界和u限界 for(i

29、nt i=0; iupbound )/遍歷左子樹(shù) upbound=bound_u;/更改已有u限界,不更改標(biāo)志 if( getbound(i, &bound_u)bound_c )/遍歷右子樹(shù) /若裝入，判斷右子樹(shù)的c限界是否大于左子樹(shù)根的c限界，是則裝入 upbound=bound_u;/更改已有u限界 curp=curp+bagi.benefit; curw=curw+bagi.weight;/從已有重量和效益加上新物品 bagi.flag=1;/標(biāo)記為裝入 void Display() cout可以放入背包的物品的編號(hào)為：; for(int i=0; i0) couti+1 ; coutendl; delete bag;4、 對(duì)比分析以上四種算法策略： 貪心算法：貪心算法中，作出的每步貪心決策都無(wú)法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。 由前面中的介紹，可以知道貪心法正確的條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。 動(dòng)態(tài)規(guī)劃算法： 全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解 。動(dòng)態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由