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

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

1、實(shí)驗(yàn)項(xiàng)目三用蠻力法、動(dòng)態(tài)規(guī)劃法和貪心法求解0/1背包問(wèn)題實(shí)驗(yàn)?zāi)康?、學(xué)會(huì)背包的數(shù)裾結(jié)構(gòu)的設(shè)計(jì)，針對(duì)不同的問(wèn)題涉及到的對(duì)象的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)也不同；2、對(duì)0-1背包問(wèn)題的算法設(shè)計(jì)策略對(duì)比與分析。實(shí)驗(yàn)內(nèi)容：0/1背包問(wèn)題是給定《個(gè)重量為{vvl，w2,...價(jià)值為{vl，v2,...，vn}的物品和一個(gè)容量為C的背包，求這些物品中的一個(gè)最有價(jià)值的子集，并且要能夠裝到背包中。在0/1背包問(wèn)題中，物品/或者被裝入背包，或者不被裝入背包，設(shè)x/表示物品/裝入背包的情況，則當(dāng)時(shí)，表示物品/沒(méi)有被裝入背包，時(shí)，表示物品/被裝入背包。根據(jù)問(wèn)題的要求，有如下約束條件和

2、目標(biāo)函數(shù)：,Zw'x>-c（式1）x-e{0,1}（1背包的數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：typedefstructobject{intn;//物品的編號(hào)intw;//物品的重量intv;//物品的價(jià)值}wup;wupwpLNj;//物品的數(shù)組，N為物品的個(gè)數(shù)intc;//背包的總重量1、蠻力法蠻力法是一種簡(jiǎn)單直接的解決問(wèn)題的方法，常常直接基于問(wèn)題的描述和所涉及的概念定義。蠻力法的關(guān)鍵是依次處理所有的元素。用蠻力法解

3、決0/1背包問(wèn)題，需要考慮給定n個(gè)物品集合的所有子集，找出所有可能的子集（總重量不超過(guò)背包容量的子集），計(jì)算每個(gè)子集的總價(jià)值，然后在他們屮找到價(jià)值最大的子集。所以蠻力法解0/1背包問(wèn)題的關(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]=m;t=t/2;

4、for(i=0;i<16;i++)//輸出保存子集的二維數(shù)組{for(j=0;j<4;j++){printf("%d”，a[i][j]);)printf(MH);}}以下要依次判斷每個(gè)子集的可行性，找出可行解：voidpanduan(intan[41，intcw[l)////判斷每?個(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].v*a[i][j];sv=sv+w

5、p

6、j].v*alij

7、jj;}if(sw<=c)cw[i]=sv;elsecw[iJ=0;在可行解中找出最優(yōu)解，即找出可行解中滿足目標(biāo)函數(shù)的最優(yōu)解。以下是找出最優(yōu)解的算法：intfindmax(intxfl61『41，intcvH)//可行解保存在數(shù)組cv屮，最優(yōu)解就足x數(shù)組屮某行的元素值相加得到的最大值{intmax;inti，j;max=O;for(i=0;i<16;i++){if(cv[i]〉max){max=cv[i];參鬱尸；}}printf("最好的組合方案是：”)；for(i=0;i<4;i++){primf("%d"，x

8、j]

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

10、背包問(wèn)題可以看作是決策一個(gè)序列(xl，x2,...，.w)，對(duì)任一變量h的決策是決定x/=l還是％/=0。在對(duì)xf-1決策后，已確定了(xl，...，xf-l)，在決策xf吋，問(wèn)題處于下列兩種狀態(tài)之一：(1)背包容量不足以裝入物品則x/=0,背包不增加價(jià)值；(2)背包容量可以裝入物品則x/=l,背包的價(jià)值增加了v/。這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì)xf決策后的背包價(jià)值。令表示在前z*(l個(gè)物品中能夠裝入容量為y(1<7

11、wzmax{V(/-l，7),j-vv,)+vj(式4)式3表明：把前而/個(gè)物品裝入容fi為0的背包和把0個(gè)物品裝入容量為