用蠻力法動(dòng)態(tài)規(guī)劃法和貪心法求解背包問題

《用蠻力法動(dòng)態(tài)規(guī)劃法和貪心法求解背包問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法設(shè)計(jì)與分析項(xiàng)目名稱：用蠻力法、動(dòng)態(tài)規(guī)劃法和貪心法求解0/1背包問題作者姓名：余武丹李紅波劉紅梅完成日期：2013年9月20日目錄第一章：簡介（Introduction）第二章：算法定義（AlgorithmSpecification）第三章：測試結(jié)果（TestingResults）第四章：分析和討論第一章：簡介（Introduction）0/1背包問題是給定n個(gè)重量為{w1,w2,…,wn}、價(jià)值為{v1,v2,…,vn}的物品和一個(gè)容量為C的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠裝到背包中。在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的

2、情況，則當(dāng)xi=0時(shí)，表示物品i沒有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標(biāo)函數(shù)：（式1）（式2）于是，問題歸結(jié)為尋找一個(gè)滿足約束條件式1，并使目標(biāo)函數(shù)式2達(dá)到最大的解向量X=(x1,x2,…,xn)。背包的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：typedefstructobject{intn;//物品的編號intw;//物品的重量intv;//物品的價(jià)值}wup;wupwp[N];//物品的數(shù)組，N為物品的個(gè)數(shù)intc;//背包的總重量第二章：算法定義（AlgorithmSpecification）1、蠻力法蠻力法是一種簡單直接的解決問題的方法，常常直接基于問題的描述和

3、所涉及的概念定義。蠻力法的關(guān)鍵是依次處理所有的元素。用蠻力法解決0/1背包問題，需要考慮給定n個(gè)物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)值，然后在他們中找到價(jià)值最大的子集。所以蠻力法解0/1背包問題的關(guān)鍵是如何求n個(gè)物品集合的所有子集，n個(gè)物品的子集有2的n次方個(gè)，用一個(gè)2的n次方行n列的數(shù)組保存生成的子集，以下是生成子集的算法：voidforce(inta[][4])//蠻力法產(chǎn)生4個(gè)物品的子集{inti,j;intn=16;intm,t;for(i=0;i<16;i++){t=i;for(j=3;j>=0;j--){m=t%2;a[i][j

4、]=m;t=t/2;}}for(i=0;i<16;i++)//輸出保存子集的二維數(shù)組{for(j=0;j<4;j++){printf("%d",a[i][j]);}printf("");}｝以下要依次判斷每個(gè)子集的可行性，找出可行解:voidpanduan(inta[][4],intcw[])////判斷每個(gè)子集的可行性，如果可行則計(jì)算其價(jià)值存入數(shù)組cw,不可行則存入0{inti,j;intn=16;intsw,sv;for(i=0;i<16;i++){sw=0;sv=0;for(j=0;j<4;j++){sw=sw+wp[j].w*a[i][j];sv=sv+wp[j].v*a[i][

5、j];}if(sw<=c)cw[i]=sv;elsecw[i]=0;}在可行解中找出最優(yōu)解，即找出可行解中滿足目標(biāo)函數(shù)的最優(yōu)解。以下是找出最優(yōu)解的算法：intfindmax(intx[16][4],intcv[])//可行解保存在數(shù)組cv中，最優(yōu)解就是x數(shù)組中某行的元素值相加得到的最大值{intmax;inti,j;max=0;for(i=0;i<16;i++){if(cv[i]>max){max=cv[i];j=i;}}printf("最好的組合方案是：");for(i=0;i<4;i++){printf("%d",x[j][i]);}returnmax;}。2、動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法將

6、待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對應(yīng)決策過程的一個(gè)階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：（1）分段：將原問題分解為若干個(gè)相互重疊的子問題；（2）分析：分析問題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；（3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。0/1背包問題可以看作是決策一個(gè)序列(x1,x2,…,xn)，對任一變量xi的決策是決定xi=1還是xi=0。

7、在對xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時(shí)，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價(jià)值；（2）背包容量可以裝入物品i，則xi=1，背包的價(jià)值增加了vi。這兩種情況下背包價(jià)值的最大者應(yīng)該是對xi決策后的背包價(jià)值。令V(i,j)表示在前i(1≤i≤n)個(gè)物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：V(i,0