實驗項目三用蠻力法動態(tài)規(guī)劃法和貪心法求解背包問題

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

2、，問題歸結(jié)為尋找一個滿足約束條件式1，并使目標函數(shù)式2達到最大的解向量X=(x1, x2, , xn)。背包的數(shù)據(jù)結(jié)構(gòu)的設(shè)計：typedef struct objectint n;/物品的編號int w;/物品的重量int v;/物品的價值wup;wup wpN;/物品的數(shù)組，N為物品的個數(shù)int c;/背包的總重量1、蠻力法蠻力法是一種簡單直接的解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。蠻力法的關(guān)鍵是依次處理所有的元素。用蠻力法解決0/1背包問題，需要考慮給定n個物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計算每個子集的總價值，然后在他們中找到價值最

3、大的子集。所以蠻力法解0/1背包問題的關(guān)鍵是如何求n個物品集合的所有子集，n個物品的子集有2的n次方個，用一個2的n次方行n列的數(shù)組保存生成的子集，以下是生成子集的算法：void force(int a164)/蠻力法產(chǎn)生4個物品的子集 int i,j; int n=16; int m,t; for(i=0;i<16;i+) t=i; for(j=3;j>=0;j-) m=t%2; aij=m; t=t/2; for(i=0;i<16;i+)/輸出保存子集的二維數(shù)組 for(j=0;j<4;j+) printf("%d ",aij); printf(

4、"n"); 以下要依次判斷每個子集的可行性，找出可行解:void panduan(int a4,int cw)/判斷每個子集的可行性，如果可行則計算其價值存入數(shù)組cw,不可行則存入0 int i,j; int n=16; int sw,sv; for(i=0;i<16;i+) sw=0; sv=0; for(j=0;j<4;j+) sw=sw+wpj.w*aij; sv=sv+wpj.v*aij; if(sw<=c) cwi=sv; else cwi=0; 在可行解中找出最優(yōu)解，即找出可行解中滿足目標函數(shù)的最優(yōu)解。以下是找出最優(yōu)解的算法：int findm

5、ax(int x164,int cv)/可行解保存在數(shù)組cv中，最優(yōu)解就是x數(shù)組中某行的元素值相加得到的最大值int max;int i,j;max=0;for(i=0;i<16;i+) if(cvi>max)max=cvi; j=i;printf("n最好的組合方案是：");for(i=0;i<4;i+)printf("%d ",xji);return max;。2、動態(tài)規(guī)劃法動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函

6、數(shù)）中，將子問題的解求解一次并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復計算。動態(tài)規(guī)劃法設(shè)計算法一般分成三個階段：（1）分段：將原問題分解為若干個相互重疊的子問題；（2）分析：分析問題是否滿足最優(yōu)性原理，找出動態(tài)規(guī)劃函數(shù)的遞推式；（3）求解：利用遞推式自底向上計算，實現(xiàn)動態(tài)規(guī)劃過程。 0/1背包問題可以看作是決策一個序列(x1, x2, , xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1, , xi-1)，在決策xi時，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不

7、增加價值；（2）背包容量可以裝入物品i，則xi=1，背包的價值增加了vi。 這兩種情況下背包價值的最大者應(yīng)該是對xi決策后的背包價值。令V(i, j)表示在前i(1in)個物品中能夠裝入容量為j（1jC）的背包中的物品的最大值，則可以得到如下動態(tài)規(guī)劃函數(shù)： V(i, 0)= V(0, j)=0 （式3） (式4)式3表明：把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包，得到的價值均為0。式4的第一個式子表明：如果第i個物品的重量大于背包的容量，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的，即物品i不能裝入背包；第二個式子表明：如果第i個物品的重量小于

8、背包的容量，則會有以下兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的價值等于把前i-1個物品裝入容量為j-wi的背包中的價值加上第i個物品的價值vi；（2）如果第i個物品沒有裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。 以下是動態(tài)規(guī)劃法求解背包問題的算法：int findmaxvalue(wup *p,int x)/x數(shù)組用來存放可行解，p是指向存放物品數(shù)組的指針 int i,j;int maxvalue;int valueN+1C+1;for(j=0;j<=C;j+)

9、value0j=0; /初始化第0行for(i=0;i<=N;i+)valuei0=0;/初始化第0列/計算數(shù)組value中各元素的值for(i=1;i<=N;i+,p+)for(j=1;j<=C;j+)if(p->w >j)valueij=valuei-1j;elsevalueij=max(valuei-1j,(valuei-1j-p->w+p->v);/max函數(shù)求兩個數(shù)當中的大者/逆推求解j=C;for(i=N;i>0;i-)if(valueij>valuei-1j)xi-1=1;/是否被選中的向量的下標也是從0開始j=j-wpi-1

10、.w;/存放物品的下標從0開始else xi-1=0;maxvalue=valueNC;/最大值return maxvalue;3、貪心法 貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），但通常能獲得近似最優(yōu)解（Near-Optimal Solution）。貪心法求解的問題的特征：（1）最優(yōu)子結(jié)構(gòu)性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)

11、構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。用貪心法求解問題應(yīng)該考慮如下幾個方面：（1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構(gòu)成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構(gòu)成解集合。（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。 （4）選

12、擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目標函數(shù)有關(guān)。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過應(yīng)付款。 背包問題至少有三種看似合理的貪心策略： （1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。

13、 （2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。 （3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。應(yīng)用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。先按單位重量價值最大對物品進行排序：void bublesort(wup wp)

14、 /把物品按單位重量價值進行從大到小的排序int i,k;wup p;int flag; for(i=1;i<N;i+) flag = 0; for (k = N-1; k >=i; k-) if (wpk-1.v/wpk-1.w<wpk.v/wpk.w)/比較物品單位重量的價值，按從大到小排序 p.n =wpk-1.n;p.v=wpk-1.v;p.w=wpk-1.w;wpk-1.n=wpk.n;wpk-1.v=wpk.v;wpk-1.w=wpk.w;wpk.n=p.n;wpk.v=p.v;wpk.w=p.w;flag=1; if(flag=0)break; 然后再用貪心策略選擇的算法如下：int tx_findmaxvalue(wup wp,int x)/ 用貪心算法找出放入背包中物品的最佳組合/wp為指向物品數(shù)組,x是存放解向量的數(shù)組int i;int cw,maxvalue;cw=C;/cw為中間變量，用來臨時存儲背包的總重量bubles