蠻力法、動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法求解01背包問題

《蠻力法、動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法求解01背包問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、一、實(shí)驗(yàn)內(nèi)容：分別用蠻力法、動(dòng)態(tài)規(guī)劃法、回溯法和分支限界法求解0/1背包問題。注：0/1背包問題：給定種物品和一個(gè)容量為的背包，物品的重量是，其價(jià)值為，背包問題是如何使選擇裝入背包內(nèi)的物品，使得裝入背包中的物品的總價(jià)值最大。其中，每種物品只有全部裝入背包或不裝入背包兩種選擇。二、所用算法的基本思想及復(fù)雜度分析：1.蠻力法求解0/1背包問題：1）基本思想：對(duì)于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時(shí)，深度優(yōu)先遍歷，搜索每一個(gè)結(jié)點(diǎn)，無論是否可能產(chǎn)生最優(yōu)解，都遍歷至葉子結(jié)點(diǎn)

2、，記錄每次得到的裝入總價(jià)值，然后記錄遍歷過的最大價(jià)值。2）代碼:#include#includeusingnamespacestd;#defineN100//最多可能物體數(shù)structgoods//物品結(jié)構(gòu)體{intsign;//物品序號(hào)intw;//物品重量intp;//物品價(jià)值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb){returna

3、=0,cw=0;intX[N],cx[N];/*蠻力法求解0/1背包問題*/intForce(inti){if(i>n-1){if(bestP

4、}intKnapSack1(intn,goodsa[],intC,intx[]){Force(0);returnbestP;}intmain(){goodsb[N];printf("物品種數(shù)n:");scanf("%d",&n);//輸入物品種數(shù)printf("背包容量C:");scanf("%d",&C);//輸入背包容量for(inti=0;i

5、a[i].p);b[i]=a[i];}intsum1=KnapSack1(n,a,C,X);//調(diào)用蠻力法求0/1背包問題printf("蠻力法求解0/1背包問題:X=[");for(i=0;i

6、則可以得到如下動(dòng)態(tài)函數(shù)：按照下述方法來劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；以此類推，直到第個(gè)階段。最后，便是在容量為的背包中裝入個(gè)物品時(shí)取得的最大價(jià)值。2）代碼：#include#includeusingnamespacestd;#defineN100//最多可能物體數(shù)structgoods//物品結(jié)構(gòu)體{intsign;//物品序號(hào)intw;//物品重量intp;//物品

7、價(jià)值}a[N];boolm(goodsa,goodsb){return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb){returna

8、i<=n;i++)//計(jì)算第i行，進(jìn)行第i次迭代for(j=1;j<=C;j++)if(j