0-1背包問題(動態(tài)規(guī)劃和貪心法實(shí)現(xiàn))

《0-1背包問題(動態(tài)規(guī)劃和貪心法實(shí)現(xiàn))》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法設(shè)計與分析實(shí)驗(yàn)報告實(shí)驗(yàn)二0-1背包問題院系：班級：計算機(jī)科學(xué)與技術(shù)學(xué)號：姓名：任課教師：成績：湘潭大學(xué)2016年5月實(shí)驗(yàn)二0-1背包問題一.實(shí)驗(yàn)內(nèi)容分別編程實(shí)現(xiàn)動態(tài)規(guī)劃算法和貪心法求0-1背包問題的最優(yōu)解，分析比較兩種算法的時間復(fù)雜度并驗(yàn)證分析結(jié)果。二．實(shí)驗(yàn)?zāi)康?、掌握動態(tài)規(guī)劃算法和貪心法解決問題的一般步驟，學(xué)會使用動態(tài)規(guī)劃和貪心法解決實(shí)際問題；2、理解動態(tài)規(guī)劃算法和貪心法的異同及各自的適用范圍。三.算法描述/*動態(tài)規(guī)劃0-1背包問題算法如下*/TemplateVoidKnapsack

2、(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c);For(intj=0;j<=jMax;j++){m[n][j]=0;}For(intj=w[n];j<=c;j++){m[n][j]=v[n];}For(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);For(intj=0;j<=jMax;j++)m[i][j]=m[i+1][j];For(intj=w[i];j<=c;j++)min[i][j]=max(m[i+1][j],m[i

3、+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];If(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);12}TemplateVoidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;i

4、][c]給出所要求的0-1背包問題的最優(yōu)解。相應(yīng)的最優(yōu)解可由算法Traceback計算如下。如果m[1][c]=m[2][c],則x1=0,否則x1=1。當(dāng)x1=0時，由m[2][c]繼續(xù)構(gòu)造最優(yōu)解。當(dāng)x1=1時，由m[2][c-w1]繼續(xù)構(gòu)造最優(yōu)解。以此類推，可構(gòu)造出相應(yīng)的最優(yōu)解（x1,x2,...,xn），時間復(fù)雜性O(shè)(n2^n)。/*貪心法0-1背包問題*/首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總

5、重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。四.算法實(shí)現(xiàn)1.數(shù)據(jù)結(jié)構(gòu)及函數(shù)說明在該問題中物品質(zhì)量W[n]和包所能承受的最大重量都是又用戶自己任意定義的，在實(shí)現(xiàn)的過程中用到一個棧來實(shí)現(xiàn)。第i件物品的選擇有兩種可能：?????????????????????????????i.??????????????物品i被選擇，這種可能性僅當(dāng)包含它不會超過方案總重量的限制時才是可行的。選中后。繼續(xù)其余物品的選擇；??????????????????????????

6、??ii.??????????????物品i不被選擇，這種可能性僅當(dāng)不包含物品i不滿足條件的情況。?現(xiàn)以第一個物品為例，當(dāng)物品1不被選擇，則問題轉(zhuǎn)變?yōu)橄鄬τ谄渌锲罚?，3，……，n），背包重量仍然為maxweight；若物品1被選擇，問題就變?yōu)殛P(guān)于最大背包重量為maxweight-w[1]的問題，現(xiàn)設(shè)r{maxweight,?maxweight-w[1]}為剩余重量的背包問題。121.源程序代碼/*動態(tài)規(guī)劃0-1背包問題*/#include#includeintV[200][

7、200];intmax(inta,intb){if(a>=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i<=n;i++)V[i][0]=0;for(j=0;j<=C;j++)V[0][j]=0;for(i=0;i<=n-1;i++)for(j=0;j<=C;j++)if(j

8、i]]+v[i]);j=C;for(i=n-1;i>=0;i--)12{if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf("選中的物品是:");for(i=0;i