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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設計與分析項 目 名 稱：用蠻力法、動態(tài)規(guī)劃法和貪心法求解0/1背包問題作者姓名：余武丹李紅波劉紅梅完成日期：2013年9月20日目錄第1章 ：簡介（Introduction）第2章 ：算法定義（Algorithm Specification）第三章：測試結(jié)果（Testing Results）第四章：分析和討論第1章 ：簡介（Introduction） 0/1背包問題是給定n個重量為w1, w2, ,wn、價值為v1, v2, ,vn的物品和一個容量為C的背包，求這些物品中的一個最有價值的子集，并且要能夠裝到背包中。在0/1背包問題中，物品i或者被裝入背包，或者不

2、被裝入背包，設xi表示物品i裝入背包的情況，則當xi=0時，表示物品i沒有被裝入背包，xi=1時，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標函數(shù)： （式1）（式2）于是，問題歸結(jié)為尋找一個滿足約束條件式1，并使目標函數(shù)式2達到最大的解向量X=(x1, x2, , xn)。背包的數(shù)據(jù)結(jié)構(gòu)的設計：typedef struct objectint n;/物品的編號int w;/物品的重量int v;/物品的價值wup;wup wpN;/物品的數(shù)組，N為物品的個數(shù)int c;/背包的總重量第二章：算法定義（Algorithm Specification）1、蠻力法蠻力法是一種簡單直接的

3、解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。蠻力法的關鍵是依次處理所有的元素。用蠻力法解決0/1背包問題，需要考慮給定n個物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計算每個子集的總價值，然后在他們中找到價值最大的子集。所以蠻力法解0/1背包問題的關鍵是如何求n個物品集合的所有子集，n個物品的子集有2的n次方個，用一個2的n次方行n列的數(shù)組保存生成的子集，以下是生成子集的算法：void force(int a4)/蠻力法產(chǎn)生4個物品的子集 int i,j; int n=16; int m,t; for(i=0;i<16;i+) t=i; for(j

4、=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("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<

5、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 findmax(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+)prin

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

7、題可以看作是決策一個序列(x1, x2, , xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1, , xi-1)，在決策xi時，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價值；（2）背包容量可以裝入物品i，則xi=1，背包的價值增加了vi。 這兩種情況下背包價值的最大者應該是對xi決策后的背包價值。令V(i, j)表示在前i(1in)個物品中能夠裝入容量為j（1jC）的背包中的物品的最大值，則可以得到如下動態(tài)規(guī)劃函數(shù)： V(i, 0)= V(0, j)=0 （式3） (式4)式3表明：把前面i個物品裝入容量為0的背

8、包和把0個物品裝入容量為j的背包，得到的價值均為0。式4的第一個式子表明：如果第i個物品的重量大于背包的容量，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的，即物品i不能裝入背包；第二個式子表明：如果第i個物品的重量小于背包的容量，則會有以下兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的價值等于把前i-1個物品裝入容量為j-wi的背包中的價值加上第i個物品的價值vi；（2）如果第i個物品沒有裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。 以下是動態(tài)規(guī)劃

9、法求解背包問題的算法：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+)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,(valu

10、ei-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.w;/存放物品的下標從0開始else xi-1=0;maxvalue=valueNC;/最大值return maxvalue;3、貪心法 貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。 這種局部

11、最優(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é)構(gòu)性質(zhì)，也稱此問題滿足最優(yōu)性原理。（2）貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來得到。用貪心法求解問題應該考慮如下幾個方面：（1）候選集合C：為了構(gòu)造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構(gòu)成候選集合。（2）解集合S：隨著

12、貪心選擇的進行，解集合S不斷擴展，直到構(gòu)成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構(gòu)成解集合。（3）解決函數(shù)solution：檢查解集合S是否構(gòu)成問題的完整解。例如，在付款問題中，解決函數(shù)是已付出的貨幣金額恰好等于應付款。 （4）選擇函數(shù)select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構(gòu)成問題的解，選擇函數(shù)通常和目標函數(shù)有關。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數(shù)feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過

13、應付款。 背包問題至少有三種看似合理的貪心策略： （1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。 （2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。 （3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量

14、，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。先按單位重量價值最大對物品進行排序，用冒泡排序算法進行排序的算法如下：void bublesort(wup wp)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.

15、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為中間變量，用來臨時存儲背包的總重量bublesort(wp);Outputwp(wp);maxvalue=0;for(i=0;i<

16、;N;i+)/對已排過序的數(shù)組，順序選擇物品是否可以放入背包if(wpi.w<cw) /如果物品的重量小于背包的重量，則放入背包 xwpi.n-1=1; /該物品被選中，對應的向量為1maxvalue=maxvalue+wpi.v;/累加價值cw=cw-wpi.w; /每放入一件物品背包的總重量減少elsexwpi.n-1=0;return maxvalue;第三章：測試結(jié)果（Testing Results）1.蠻力法測試結(jié)果：輸入完畢后按Enter鍵有如下結(jié)果：2.動態(tài)規(guī)劃法調(diào)試結(jié)果3. 貪心法調(diào)試結(jié)果：(1).空間最優(yōu)的貪心策略結(jié)果(2).價格最優(yōu)的貪心策略結(jié)果(3).價格空間比最優(yōu)

17、的貪心策略結(jié)果第四章：分析和討論算法的時間復雜度和空間復雜度的分析，對算法進一步改進的討論。附錄：源代碼（基于C語言的）1.蠻力法求解01背包問題源程序：#include "stdafx.h"#include "stdlib.h" #include "stdio.h"#define N 4#define max 10struct product int id; /物品編號int price;/物品價格 int weight;/物品重量 int flag;/物品標號 char name20;/物品名稱PN;void math()/尋找最

18、優(yōu)組合的方法 int i,j,k;/定義三個循環(huán)變量，依次求出最大價值的物品組合及物品最大價值 int imax,jmaxa,jmaxb,kmaxa,kmaxb,kmaxc; int maxvalue1, maxvalue2, maxvalue3, maxvalue4; int maxnum; maxvalue1=0; imax=0; /第一次比較找出價值最大的商品，并把該商品價值賦給maxvalue1，商品編號賦給maxi for(i=0;i<N;i+) if(Pi.weight<max&&Pi.price>maxvalue1) maxvalue1=Pi.p

19、rice; imax=i; /從剩下的商品中找出較大價值，并存放在maxvalue2 maxvalue2=0; for(i=0;i<N;i+) for(j=i+1;j<N;j+) if(Pi.weight+Pj.weight<max)&&(Pi.price+Pj.price>maxvalue2) maxvalue2=Pi.price+Pj.price; jmaxa=i; jmaxb=j; /從剩下的商品中找出較大價值，并存放在maxvalue3 maxvalue3=0; for(i=0;i<N;i+) for(j=i+1;j<N;j+) fo

20、r(k=i+2;k<N;k+) if(Pi.weight+Pj.weight+Pk.weight<max)&&(Pi.price+Pj.price+Pk.price>max) maxvalue3=Pi.price+Pj.price+Pk.price; kmaxa=i; kmaxb=j; kmaxc=k; /如果所有的物品總重量都小于背包能夠承受的最大重量，則把所有物品放入背包 if(P0.weight+P1.weight+P2.weight+P3.weight<max) maxvalue4=P0.price+P1.price+P2.price+P3.pr

21、ice; printf("%s,%d,%d",P0.name,P0.weight,P0.price); printf("%d",maxvalue4);/把最大價值放在maxvalue4變量中 /輸出組合商品的信息 maxnum=maxvalue1; if(maxvalue2>maxvalue1) maxnum=maxvalue2; if(maxvalue3>maxnum) maxnum=maxvalue3; printf("%d",maxnum); if(maxnum=maxvalue1) printf("%d&

22、quot;,maxnum); if(maxnum=maxvalue2) printf("%s,%d,%dn",P,Pjmaxa.weight,Pjmaxa.price); printf("%s,%d,%dn",P,Pjmaxb.weight,Pjmaxb.price); printf("%d",maxnum); system("pause");void scannum()/輸入物品信息 int i=0;printf("t請輸入物品信息(N=4):tn");

23、for(i=0;i<N;i+) Pi.id=i+1; printf("t物品名稱： "); scanf("%s",&P); printf("t物品重量： "); scanf("%d",&Pi.weight); printf("t物品價格:"); scanf("%d",&Pi.price); Pi.flag=0; printf("n"); int main()/主函數(shù)，while循環(huán)變量選擇你要進行的操作int k;

24、while(1) printf("請選擇操作:n");printf("1.輸入物品的信息n");printf("2.求取最佳方案n");scanf("%d",&k);switch (k)case 1:scannum();break;/調(diào)用scannum()方法完成物品信息的輸入case 2:math(); break;/調(diào)用math()方法完成最佳組合及最大價值計算 default: return -1;/否則返回-1system("cls");/CLS命令是清除屏幕上所有的文字retu

25、rn 0;2. 動態(tài)規(guī)劃法求解01問題源程序：/動態(tài)規(guī)劃法#include "StdAfx.h"#include<stdio.h>int c10100;/*對應每種情況的最大價值*/int knapsack(int m,int n) int i,j,w10,p10; printf("請輸入每個物品的重量,價值：n"); for(i=1;i<=n;i+) scanf("%d,%d",&wi,&pi); for(i=0;i<10;i+) for(j=0;j<100;j+) cij=0;/*初始

26、化數(shù)組*/ for(i=1;i<=n;i+) for(j=1;j<=m;j+) if(wi<=j) /*如果當前物品的容量小于背包容量*/ if(pi+ci-1j-wi>ci-1j) /*如果本物品的價值加上背包剩下的空間能放的物品的價值*/ /*大于上一次選擇的最佳方案則更新cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; return(cnm); int main() int m,n;int i,j;printf("請輸入背包的承重量,物品的總個數(shù)：n"); scanf("%d

27、,%d",&m,&n); printf("旅行者背包能裝的最大總價值為%d",knapsack(m,n); printf("n"); return 0;3. 貪心法求解01背包問題源程序#include "stdafx.h"#include <stdio.h>#include <stdlib.h>typedef structchar name10;int weight;int price;Project;Project *Input(Project *wp,int TotalNum,i

28、nt TotalWeight)int i,j,Way,GoBack,RealWeight,RealPrice,TotalPrice;Project temp;doprintf("請選擇：n");printf("1.空間最優(yōu)n");printf("2.價格最優(yōu)n");printf("3.價格空間比最優(yōu)n");scanf("%d",&Way);switch(Way)case 1:/選擇空間最優(yōu)for(i=0;i<TotalNum;i+)for(j=0;j<TotalNum-i-1

29、;j+)if(wpj.weight>wpj+1.weight)temp=wpj;wpj=wpj+1;wpj+1=temp;break;case 2:/選擇價格最優(yōu)for(i=0;i<TotalNum;i+)for(j=0;j<TotalNum-i-1;j+)if(wpj.price>wpj+1.price)temp=wpj;wpj=wpj+1;wpj+1=temp;break;case 3:/價格空間比最優(yōu)for(i=0;i<TotalNum;i+)for(j=0;j<TotalNum-i-1;j+)if(float)wpj.price/(float)wpj.weight<(float)wpj+1.price/(float)wpj+1.weight)temp=wpj;wpj=wpj+1;wpj+1=temp;break;default:printf("輸入錯誤!n");exit(1);i=0;RealWeight=wp0.weight;TotalPrice=wp0.price;printf("被裝入背包的物品是:n(