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

1、 信息技術(shù)學院 算法設(shè)計與分析課程考查論文 題 目 0 0- -1 1 背包問題的算法設(shè)計謀略比照與分析 專業(yè) 計算機科學與技術(shù) 班級 20062006 級軟件方向 學 號 061124015061124015 姓 名 _ 劉翠蘭 _ 任 課教師 _ 宋振方 _ 完成日期 20212021 年 1212 月 3131 日2006級軟件方向算法設(shè)計與分析課程考查論文 第1頁共14頁 0-1背包問題的算法設(shè)計謀略比照與分析 0引言 對于計算機科學來說， 算法的概念是至關(guān)重要的， 例如，在一個大型軟件系統(tǒng)的開發(fā)中， 設(shè)計出 有效的算法將起決定性的作用。算法是解決問題的一種方法或一個過程。程序是算法用

2、某種設(shè)計語 言具體實現(xiàn)描。計算機的普及極大的改變了人們的生活。目前，各行業(yè)、各領(lǐng)域都廣泛采用了計算 機信息技術(shù)，并由此產(chǎn)生出開發(fā)各種應(yīng)用軟件的需求。為了以最小的本錢、最快的速度、最好的質(zhì) 量開發(fā)出適合各種應(yīng)用需求的軟件，必須遵循軟件工程的原那么。設(shè)計一個高效的程序不僅需要編程 小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的素算法，這正是計算機科學領(lǐng)域數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計 所研究的主要內(nèi)容。 1算法復雜性分析的方法介紹 算法復雜性是算法運行所需要的計算機資源的量，需要時間資源的量稱為 時間復雜性，需要的 空間資源的量稱為空間復雜性。這個量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本 身的函數(shù)。如

3、果分別用 M I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用 決示復 雜性，那么，應(yīng)該有 C=F(N,I,A)。一般把時間復雜性和空間復雜性分開，并分別用 訝日S來表示，那么 有：T=T(N,I)和S=S(N,I)。(通常，讓A急含在復雜性函數(shù)名當中 最壞情況下的時間復雜性： k Tmax(N) = max T (N , I ) = max 值(N , I ) I - D N I z D N i _1 最好情況下的時間復雜性： k MN) = min T(N , I) = min (N ,I ) r DN R DN 平均情況下的時間復雜性： Tavg(N) = Z P(I)T(N,

4、I) = Z P(I )L ti6i(N,I) I DN D N i 其中D睡規(guī)模為N勺合法輸入的集合；I*是DN中使T(N, I*) 到達Tmax(N)的合法輸入； 是中使 T(N,)到達Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入 I的概率。 算法復雜性在漸近意義下的階： 漸近意義下的記號：Q Q、。、o設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。 邸定義：如果存在正的常數(shù) 3日自然數(shù)N0,使得當NN0時有f(N) Cg(N)，那么稱函數(shù)f(N)當N分大 時下有界，且g(N)是它的一個下界，記為f(N)= Q (g(N)。即f(N)的階不低于g(N)的階。 0的定義：定義

5、f(N)= 0 (g(N)當且僅當f(N)=O(g(N) 且f(N)= Q (g(N)。此時稱f(N)與g(N)同階。 。的定義：對于任意給定的 0,都存在正整數(shù)N0,使得當N瀏0寸有f(N)/Cg(N) &，那么稱函數(shù)f(N) 當N充分大時的階比g(N)低，記為f(N)=o(g(N)。 k = tie(N, I i z! * = T(N,I )= T(N,I ) = T(N ,I )= T(N ,I ) =寸 ti6i(N , I ) i =1 0-1背包問題的算法設(shè)計謀略比照與分析 第2頁共14頁 例如，4NlogN+7=o(3N2+4NlogN+7)。 2常見的算法分析設(shè)計謀略介

6、紹 2.1遞歸與分治策略 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各 個擊破，分而治之。對這 k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，那么再劃分為 k個子問 題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問題的 解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。由于分治法產(chǎn)生的子問題往 往是原來問題的較小規(guī)模，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復應(yīng)用分治手段， 可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易求出其解。由此 自然引出遞歸算法。分治與遞歸像是一對攣生

7、兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許 多高效的算法。 2.2動態(tài)規(guī)劃 動態(tài)規(guī)劃算法與分治法類似，其根本思想也是將待求解問題分解成假設(shè)干個子問題。但是經(jīng)分解得 到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有 些子問題被重復計算了許屢次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的 答案，就可以防止大量重復計算，從而得到多項式時間算法。 動態(tài)規(guī)劃的一般步驟：找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 遞歸地定義最優(yōu)值。 以自底向上的方式計算出最優(yōu)值。 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。 2.3貪心算法 顧名思義，貪心算法總是作出在當前

8、看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮， 它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問題，用貪心算法更簡 單、更直接且解題效率更高。當然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法 不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最 小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很 好近似。 2.4回溯法 有許多問題，當需要找出它的解集或者要求答復什么解是滿足某些約束條件的最正確解時， 往往要使 用回溯法。 回溯法的根本做法是搜索，或是一種組織得井井有條的，能防止不必要搜索

9、的窮舉式搜索法。這 種方法適用于解一些組合數(shù)相當大的問題。 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間 樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，那么跳過對該結(jié)點為根的子樹 的搜索，逐層向其祖先結(jié)點回溯；否那么，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 問題的解向量：回溯法希望一個問題的解能夠表示成一個 n元式(x1,x2,xn)的形式。 顯約束：對分量xi的取值限定。 隱約束：為滿足問題的解而對不同分量之間施加的約束。 解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空 間。2006級軟件方向算法設(shè)

10、計與分析課程考查論文 第11頁共14頁 3 2.5分支限界法 分支限界法常以廣度優(yōu)先或以最小消耗(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限 界法中，每一個活結(jié)點只有一次時機成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所 有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點 被參加活結(jié)點表中。 此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù) 到找到所需的解或活結(jié)點表為空時為止。 從活結(jié)點表中選擇下一擴展結(jié)點的不同方式導致不同的分 支限界法： 隊列式(FIFO)分支限界法：按照隊列先進先出( FIFO)原那么

11、選取下一個節(jié)點為擴展節(jié)點。 優(yōu)先隊列式分支限界法：按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。 最大優(yōu)先隊列：使用最大堆，表達最大效益優(yōu)先 最小優(yōu)先隊列：使用最小堆，表達最小費用優(yōu)先 3結(jié)合0-1背包問題詳述動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法解決問題的過程 0-1背包問題：給定 n種物品和一個背包。物品 i的重量是 Wi,其價值為Vi ,背包的容量是 c。 問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中的物品總價值最大。在選擇裝入背包的物品時， 對每種物品i只能有兩種選擇，裝入包或者不裝入。不能物品 i裝入包屢次，也不能之裝入局部的 物品io 3.1動態(tài)規(guī)劃算法 問題描述

12、 此問題的形式化描述是， 給定c0,Wi0,Vi0 , 1 n,要求找出一個 n元0-1向量(x1 , x2, xn), Xi W0,1,1 3Mn,使得 WiXiWiXi 苴 c ,c ,而且 ViXiViXi 到達最大。因此 0-1背包問題是一個特殊的整 i * i注 n 數(shù)規(guī)劃問題： max Vj xj i A I ,二-WiXi 竺C xi 0,1, 1 i . n 算法描述： 設(shè)所給0-1背包問題的子問題 max E (Vk * Xk) k=i.n ; ma近(Vk * Xk) = j (k=i.n ) ; Xk 0 , 1, i =k = wi 0 = j = wn 0 = j w

13、n #include #define Max 101 int mMaxMax,wMax,vMax,xMax; void Knapsack(int c,int n) ( int jMax=min(wn-1,c); m(i , j) = maxm(i+1 m(i , j) = m(i+1,j) m(n,j) = Vn m(n,j) = 0 程序： 0-1背包問題的算法設(shè)計謀略比照與分析 第4頁共14頁 for(int j=0;j=jMax;j+)mnj=0; for(int j=wn;j1;i-) ( jMax=min(wi-1,c); for(int j=0;jjMax;j+)mij=mi+1j

14、; 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

15、=1;i=n;i+)printf(%d ,xi); printf(n); return 0; 3.2貪心算法 問題描述： 假定有n個物體和一個背包，物體 i有質(zhì)量wi,價值為pi ,而背包的載荷能力為 M 假設(shè)將物體i的一局部xi ( 1=i=n,0=xi=1) 裝入背包中，那么有價值pi*xi 。在約束條件 (w1*x1+w2*x2+ . +wn*xn)=M 下 使目標(p1*x1+p2*x2+ . +pn*xn)到達 極大，此處 0=xi0,1=i=n. 這個問題稱為背包問題( Knapsack problem )。 算法描述 首先計算每種物品單位重量的價值 Vi/Wi，然后，依貪心選擇策

16、略，將盡可能多的 單位重 量價值最高 的物品裝入背包。假設(shè)將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 C,那么選 擇單位重量價值次高的物品并盡可能多地裝入背包。 依此策略一直地進行下去, 程序代碼： #include struct goodinfo float p; / 物品效益 float w; / 物品重量 float X; / 物品該放的數(shù)量 int flag; / 物品編號 ; / 物品信息結(jié)構(gòu)體 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; g

17、oodsi+1=goods0; / 按物品效益，重量比值做升序排列 void bag(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)/ 當該物品重量大與剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/ 確定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/ 該物品所要放的量 for(j=2;j=n;j+) /* 按物品編號做降序排列*/ goods0=goodsj; i=

18、j-1; while (goods0.flaggoodsi.flag) ( goodsi+1=goodsi; i-； goodsi+1=goods0; lllllllllllllllllllllllllllllllllllllllllll cout最優(yōu)解為:endl; for(i=1;i=n;i+) ( cout 第i件物品要放:; coutgoodsi.Xendl; void main() ( cout|- 運用貪心法解背包問題 - |endl; cout|-power by zhanjiantao(028054115)-|endl; cout|- |endl; int j; int n;

19、float M; goodinfo *goods;ll 定義一個指針 while(j) ( coutn; goods=new struct goodinfo n+1;ll coutM; coutendl; int i; for(i=1;i=n;i+) ( goodsi.flag=i; cout 請輸入第igoodsi.w; cout 請輸入第igoodsi.p; goodsi.p=goodsi.plgoodsi.w;ll 得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianend

20、l; coutpress to exitj; 3.3回溯算法 問題描述： 對于0-1背包問題回溯法的一個實例， n=4, c=7 , p=9,10,7,4,w=3,5,2,1.這4個物品的單位重量價 值分別為3,2,3,5,4.以物品為單位價值的遞減序裝入物品。先裝入物品 4,然后裝入物品3和1.裝入 這3個物品后，剩余的背包容量為1,只能裝入0.2的物品2.由此可得到一個解為 x=1,0,2,1,1,其相 應(yīng)的價值為22.盡管這不是一個可行解，但可以證明其價值是最有大的上界。因此，對于這個實例， 最優(yōu)值不超過22. 算法描述：0-l背包問題是子集選取問題。一般情況下， 0-1背包問題是NP難

21、題。0-1背包問題的 解空間可用子集樹表示。解 0-1背包問題的回溯法與裝載問題的回溯法十分類似。在搜索解空間樹 時，只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進入其左子樹。當右子樹有可能包含最優(yōu)解時才進 入右子樹搜索。否那么將右子樹剪去。設(shè) r是當前剩余物品價值總和； cp是當前價值；bestp是當前 最優(yōu)價值。當cp+r bestp時，可剪去右子樹。計算右子樹中解的上界的更好方法是將剩余物品依 其單位重量價值排序，然后依次裝入物品，直至裝不下時，再裝入該物品的一局部而裝滿背包。由 此得到的價值是右子樹中解的上界。 程序： #include using namespace std; class

22、Knap friend 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)值 2006級軟件方向算法設(shè)計與分析課程考查論文 第11頁共1

23、4頁 7 int *bestx;/ 當前最優(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 Obj

24、ect ( friend int Knapsack(int p,int w,int c,int n); public: 0-1背包問題的算法設(shè)計謀略比照與分析 第8頁共14頁 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(i=1;i=n;i+) ( Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi

25、; 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;i+) ( K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; 2006級

26、軟件方向算法設(shè)計與分析課程考查論文 第11頁共14頁 9 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 背包問題- 回溯法 endl; cout by zbqplayer endl; while(k) ( cout請輸入背包容量(c) : c; cout請輸入物品的個

27、數(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; coutKnapsack(p,w,c,n)endl; couts 重新開始endl; coutq 退出k; 3.4分支限界 問題描述： 有N個物品和一個可以容納 M重量的背包，每種物品I的重量為 WEIGHT 一個只能全放入或者 0-1背包問題的算法設(shè)計

28、謀略比照與分析 第10頁共14頁 不放入，求解如何放入物品， 可以使背包里的物品的總效益最大。 對物品的選取與否構(gòu)成一棵解樹， 左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優(yōu)解，并用結(jié)點上界殺死不符合要求 的結(jié)點。 算法描述： 首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu) 先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿 剩余容量的價值和。算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行 結(jié)點，那么將它參加到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅 當右兒子

29、結(jié)點滿足上界約束時才將它參加子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最 優(yōu)值。 程序： #include struct good int weight; int benefit; int flag;/ 是否可以裝入標記 ; int number=0;/ 物品數(shù)量 int upbound=0; int curp=0, curw=0;/ 當前效益值與重量 int maxweight=0; good *bag=NULL; void Init_good() bag=new good number; for(int i=0; inumber; i+) ( cout請輸入第件i+1bagi.wei

30、ght; cout請輸入第件i+1bagi.benefit; bagi.flag=0;/ 初始標志為不裝入背包 coutendl; int getbound(int num, int *bound_u)/ 返回本結(jié)點的 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*(maxweig

31、ht-w)/bagnum.weight); void LCbag() ( int bound_u=0, bound_c=0;/ 當前結(jié)點的 c限界和u限界 for(int i=0; iupbound )/ 遍歷左子樹 upbound=bound_u;/ 更改已有u限界，不更改標志 if( getbound(i, &bound_u)bound_c )/ 遍歷右子樹 /假設(shè)裝入，判斷右子樹的 c限界是否大于左子樹根的 c限界，是那么裝入 ( upbound=bound_u;/ 更改已有 u 限界 curp=curp+bagi.benefit; curw=curw+bagi.weight;/

32、 從已有重量和效益加上新物品 bagi.flag=1;/ 標記為裝入 void Display() ( cout可以放入背包的物品的編號為： ; for(int i=0; i0) couti+1; coutendl; delete bag; 4、比照分析以上四種算法策略： 貪心算法：貪心算法中，作出的每步貪心決策都無法改變， 因為貪心策略是由上一步的最優(yōu)解推導 下一步的最優(yōu)解，而上一部之前的最優(yōu)解那么不作保存。 由前面中的介紹，可以知道貪心法正確的 條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。 動態(tài)規(guī)劃算法：全局最優(yōu)解中一定包含某個局部最優(yōu)解， 但不一定包含前一個局部最優(yōu)解， 因此需 要記錄之前的所有最優(yōu)解 。動態(tài)規(guī)劃