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

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

2、應(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)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用NI和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用榮示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用有DS來表示，則有：T=T(N,I)和S=S(N,I)。(通常，

3、讓A急含在復(fù)雜性函數(shù)名當(dāng)中最壞情況下的時(shí)間復(fù)雜性：kTmax(N)=maxT(N,I)=maxtie,(NI-Dnizdni_i最好情況下的時(shí)間復(fù)雜性：I)k一*633,I)iW*=T(N,I)k=、tieMN,I)i:1=T(N,I)Tmin(N)=minT(N,I)=mint,ei(N,I)minI二d1-DNNi-：1平均情況下的時(shí)間復(fù)雜性:kTavg(N)=、P(I)T(N,I)=、P(Iytie(N,I)I-Dn1-Dni7其中DN規(guī)卞莫為NW合法輸入白集合；I*是DN中使T(N,I*)達(dá)到Tmax(N)的合法輸入；是中使T(N,)達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)

4、用中出現(xiàn)輸入I的概率。算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：Q、。、o設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O勺定義：如果存在正的常數(shù)CF口自然數(shù)N0,使得當(dāng)NaN0時(shí)有f(N)ECg(N),則稱函數(shù)f(N)當(dāng)N分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N)。即f(N)的階不高于g(N)的階。根據(jù)O勺定義，容易證明它有如下運(yùn)算規(guī)則：(1)0+O(g)=O(max(f,g);(2)0+O(g)=O(f+g);(3)0(f)0(g)=0(fg);(4)如果g(N)=O(f(N),則O(f)+O(g)=O(f);(5)0(Cf(N)=0(f(N),其中B一個(gè)正的常

5、數(shù)；(6)f=0(f)。的定義：如果存在正的常數(shù)5口自然數(shù)NO,使彳#當(dāng)N米0時(shí)有f(N)Cg(N),則稱函數(shù)f(N)當(dāng)N分大時(shí)下有界，且g(N)是它的一個(gè)下界，記為f(N)=Q(g(N)。即f(N)的階不低于g(N)的階。0的定義：定義f(N)=0(g(N)當(dāng)且僅當(dāng)f(N)=O(g(N)且f(N)=Q(g(N)。此時(shí)稱f(N)與g(N)同階。o的定義：對于任意給定的0,者B存在正整數(shù)N0,使彳導(dǎo)當(dāng)N小0寸有f(N)/Cg(N)0,Wi0,Vi0,1in,要求找出一個(gè)n元0-1向量(x1,x2,xn),nnXiw0,1,1in,使得WWiXiMc,而且工ViXi達(dá)到最大。因此0-1背包問題是一

6、個(gè)特殊的整i土一n數(shù)規(guī)劃問題：max、Vixii：4W.:二WiXi三CIi土xi0,1,1i=wi0=j=wn0=jwnm(n,j)=Vnm(n,j)=0程序：#include#defineMax101intmMaxMax,wMax,vMax,xMax;voidKnapsack(intc,intn)(intjMax=min(wn-1,c);for(intj=0;j=jMax;j+)mnj=0;for(intj=wn；j1;i-)(jMax=min(wi-1,c);for(intj=0;jjMax;j+)mij=mi+1j;for(intj=wi;j=w1)m1c=max(m1c,m2c-w1

7、+v1);voidTraceback(intc,intn)(for(inti=0;in;i+)if(mic=mi+1c)xi=0;elsexi=1;c-=wi;xn=(mnc)?1:0;intmain()intn,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+)printf(%d,xi);printf(n);return0;3.2貪心算法問題描述：假定有n個(gè)物體和一個(gè)背包，物體i有質(zhì)量wi,價(jià)值為pi,而背包的

8、載荷能力為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è)問題稱為背包問題(Knapsackproblem)。算法描述首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi,然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C,則選直到背包裝滿為止。擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去,程序代碼：#includestructgoodin

9、fofloatp;物品效益floatw;物品重量floatX;/物品該放的數(shù)量intflag;/物品編號(hào));/物品信息結(jié)構(gòu)體voidInsertionsort(goodinfogoods,intn)intj,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;)goodsi+1=goods0;/按物品效益，重量比值做升序排列voidbag(goodinfogoods,floatM,intn)floatcu;inti,j;for(i=1;i=n;i+)goodsi.X=0;cu=M;/背包剩余容量for(i=1;icu)/當(dāng)該物品重量大與剩余容量跳出break;good

10、si.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=goodsi;i-；goodsi+1=goods0;/cout最優(yōu)解為:endl;for(i=1;i=n;i+)(cout第i件物品要放：coutgoodsi.Xendl;voidmain()(cout|運(yùn)用貪心法解背包問題|endl;cout|-powerbyzhanjiantao(

11、028054115)-|endl;cout|endl;intj;intn;floatM;goodinfo*goods;/定義一個(gè)指針while(j)(coutn;goods=newstructgoodinfon+1;/coutM;coutendl;inti;for(i=1;i=n;i+)goodsi.flag=i;cout請輸入第igoodsi.w;cout請輸入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比coutendl;Insertionsort(goods,n);bag(goods,M,n);coutpresstorunagiane

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

13、樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類似。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹。當(dāng)右子樹有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹搜索。否則將右子樹剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+rwbestp時(shí)，可剪去右子樹。計(jì)算右子樹中解的上界的更好方法是將剩余物品依其單位重量價(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一部分而裝滿背包。由此得到的價(jià)值是右子樹中解的上界。程序：#includeusingnamespacestd;classKnapfriendintKnapsack(intp,intw,in

14、tc,intn);public:voidprint()for(intm=1;m=n;m+)coutbestxm;coutendl;private:intBound(inti);voidBacktrack(inti);intc;/背包容量intn;/物品數(shù)int*w;/物品重量數(shù)組int*p;/物品價(jià)值數(shù)組intcw;當(dāng)前重量intcp;/當(dāng)前價(jià)值intbestp;/當(dāng)前最優(yōu)值int*bestx;/當(dāng)前最優(yōu)解int*x;/當(dāng)前解)；intKnap:Bound(inti)(/計(jì)算上界intcleft=c-cw;/剩余容量intb=cp;/以物品單位重量價(jià)值遞減序裝入物品while(i=n&wi=c

15、left)(cleft-=wi;b+=pi;i+;)/裝滿背包if(in)(if(bestpcp)(for(intj=1;j=n;j+)bestxj=xj;bestp=cp;)return;)if(cw+wibestp)/搜索右子樹(xi=0;Backtrack(i+1);)classObject(friendintKnapsack(intp,intw,intc,intn);public:intoperator=a.d);)private:intID;floatd;);intKnapsack(intp,intw,intc,intn)(/為Knap:Backtrack初始化intW=0;intP

16、=0;inti=1;Object*Q=newObjectn;for(i=1;i=n;i+)(Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;)if(W=c)returnP;/裝入所有物品/依物品單位重量排序floatf;for(i=0;in;i+)for(intj=i;jn;j+)(if(Qi.dQj.d)(f=Qi.d;Qi.d=Qj.d;Qj.d=f;)KnapK;K.p=newintn+1;K.w=newintn+1;K.x=newintn+1;K.bestx=newintn+1;K.x0=0;K.bestx0=0;for(i=1;i=n;i+)(K.pi=

17、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();deleteQ;deleteK.w;deleteK.p;returnK.bestp;voidmain()(int*p;int*w;intc=0;intn=0;inti=0;chark;cout0-1背包問題回溯法endl;coutbyzbqplayerendl;while(k)(cout請輸入背包容量(c):c;cout請輸入物品的個(gè)數(shù)(n):n;p=newintn+1;w=newintn+1;p0=0;w0=0;co

18、ut請輸入物品的價(jià)值(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個(gè)物品和一個(gè)可以容納M重量的背包，每種物品I的重量為WEIGHT一個(gè)只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。對物品的選取與否構(gòu)成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優(yōu)解，并用結(jié)點(diǎn)上界殺死不符合要求的

19、結(jié)點(diǎn)。算法描述：首先，要對輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。程序：#includestructgoodintweight;intbenefit;intflag;/是否可以裝入標(biāo)記;intnumber=0;物品

20、數(shù)量intupbound=0;intcurp=0,curw=0;/當(dāng)前效益值與重量intmaxweight=0;good*bag=NULL;voidInit_good()bag=newgoodnumber;for(inti=0;inumber;i+)(cout請輸入第件i+1bagi.weight;cout請輸入第件i+1bagi.benefit;bagi.flag=0;/初始標(biāo)志為不裝入背包c(diǎn)outendl;intgetbound(intnum,int*bound_u)/返回本結(jié)點(diǎn)的c限界和u限界(for(intw=curw,p=curp;numnumber&(w+bagnum.weight

21、)=maxweight;num+)(w=w+bagnum.weight;p=w+bagnum.benefit;*bound_u=p+bagnum.benefit;return(p+bagnum.benefit*(maxweight-w)/bagnum.weight);voidLCbag()(intbound_u=0,bound_c=0;/當(dāng)前結(jié)點(diǎn)的c限界和u限界for(inti=0;iupbound)/遍歷左子樹upbound=bound_u;/更改已有u限界，不更改標(biāo)志if(getbound(i,&bound_u)bound_c)/遍歷右子樹/若裝入，判斷右子樹的c限界是否大于左子樹根的c限

22、界，是則裝入(upbound=bound_u;/更改已有u限界curp=curp+bagi.benefit;curw=curw+bagi.weight;/從已有重量和效益加上新物品bagi.flag=1;/標(biāo)記為裝入voidDisplay()(cout可以放入背包的物品的編號(hào)為：;for(inti=0;i0)couti+1;coutendl;deletebag;)4、對比分析以上四種算法策略：貪心算法：貪心算法中，作出的每步貪心決策都無法改變，因?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)移方程，即如何由以求出的局部最優(yōu)解來推導(dǎo)全局最優(yōu)解。邊界條件：即最簡單的，可以直接得出的局部最優(yōu)解回溯算法：回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。它適用于解一些組合數(shù)較大的問題。分支限界法：分支限界法的搜索策略是，在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)，然后在從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)函數(shù)值，從