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

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

2、的最大價值。2）代碼:#include<iostream>#include<algorithm>using namespace std;#define N 100/最多可能物體數(shù)struct goods/物品結(jié)構(gòu)體int sign;/物品序號int w;/物品重量int p;/物品價值aN;bool m(goods a,goods b)return (a.p/a.w)>(b.p/b.w);int max(int a,int b)return a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;/*蠻力法求解0/1背包問題

3、*/int Force(int i)if(i>n-1)if(bestP<cp&&cw+ai.w<=C)for (int k=0;k<n;k+)Xk=cxk;/存儲最優(yōu)路徑bestP=cp;return bestP;cw=cw+ai.w;cp=cp+ai.p;cxi=1;/裝入背包Force(i+1);cw=cw-ai.w;cp=cp-ai.p;cxi=0;/不裝入背包Force(i+1);return bestP;int KnapSack1(int n,goods a,int C,int x)Force(0);return bestP;int main(

4、)goods bN;printf("物品種數(shù)n: ");scanf("%d",&n);/輸入物品種數(shù)printf("背包容量C: ");scanf("%d",&C);/輸入背包容量for (int i=0;i<n;i+)/輸入物品i的重量w及其價值vprintf("物品%d的重量w%d及其價值v%d: ",i+1,i+1,i+1);scanf("%d%d",&ai.w,&ai.p);bi=ai;int sum1=KnapSack1(n,a

5、,C,X);/調(diào)用蠻力法求0/1背包問題printf("蠻力法求解0/1背包問題:nX= ");for(i=0;i<n;i+)cout<<Xi<<" "/輸出所求Xn矩陣printf("裝入總價值%dn",sum1);bestP=0,cp=0,cw=0;/恢復(fù)初始化3）復(fù)雜度分析：蠻力法求解0/1背包問題的時間復(fù)雜度為：。2.動態(tài)規(guī)劃法求解0/1背包問題：1）基本思想：令表示在前個物品中能夠裝入容量為的背包中的物品的最大值，則可以得到如下動態(tài)函數(shù)：按照下述方法來劃分階段：第一階段，只裝入前1個物品，確定在

6、各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；以此類推，直到第個階段。最后，便是在容量為的背包中裝入個物品時取得的最大價值。 2）代碼： #include<iostream> #include<algorithm> using namespace std; #define N 100/最多可能物體數(shù) struct goods/物品結(jié)構(gòu)體 int sign;/物品序號 int w;/物品重量 int p;/物品價值 aN; bool m(goods a,goods b) return (a.p/a.w)>(

7、b.p/b.w); int max(int a,int b) return a<b?b:a; int n,C,bestP=0,cp=0,cw=0; int XN,cxN; int KnapSack2(int n,goods a,int C,int x) int VN10*N; for(int i=0;i<=n;i+)/初始化第0列 Vi0=0; for(int j=0;j<=C;j+)/初始化第0行 V0j=0; for(i=1;i<=n;i+)/計算第i行，進行第i次迭代 for(j=1;j<=C;j+) if(j<ai-1.w) Vij=Vi-1j; e

8、lse Vij=max(Vi-1j,Vi-1j-ai-1.w+ai-1.p); j=C;/求裝入背包的物品 for (i=n;i>0;i-) if (Vij>Vi-1j) xi-1=1; j=j-ai-1.w; elsexi-1=0; return VnC;/返回背包取得的最大價值 int main() goods bN; printf("物品種數(shù)n: "); scanf("%d",&n);/輸入物品種數(shù) printf("背包容量C: "); scanf("%d",&C);/輸入背包容量

9、 for (int i=0;i<n;i+)/輸入物品i的重量w及其價值v printf("物品%d的重量w%d及其價值v%d: ",i+1,i+1,i+1); scanf("%d%d",&ai.w,&ai.p); bi=ai; int sum2=KnapSack2(n,a,C,X);/調(diào)用動態(tài)規(guī)劃法求0/1背包問題 printf("動態(tài)規(guī)劃法求解0/1背包問題:nX= "); for(i=0;i<n;i+) cout<<Xi<<" "/輸出所求Xn矩陣 print

10、f("裝入總價值%dn",sum2); for (i=0;i<n;i+) ai=bi; /恢復(fù)aN順序 3）復(fù)雜度分析:動態(tài)規(guī)劃法求解0/1背包問題的時間復(fù)雜度為：。3.回溯法求解0/1背包問題：1）基本思想：回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實際上不可能產(chǎn)生所需解的活結(jié)點，以減少問題的計算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。對于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時，只要其左兒子結(jié)點是一個可行結(jié)點，搜索就進入

11、左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時就進入右子樹搜索。 2）代碼: #include<iostream> #include<algorithm> using namespace std; #define N 100/最多可能物體數(shù) struct goods/物品結(jié)構(gòu)體 int sign;/物品序號 int w;/物品重量 int p;/物品價值 aN; bool m(goods a,goods b) return (a.p/a.w)>(b.p/b.w); int max(int a,int b) return a<b?b:a; int n,C,bestP=0

12、,cp=0,cw=0; int XN,cxN; int BackTrack(int i) if(i>n-1) if(bestP<cp) for (int k=0;k<n;k+)Xk=cxk;/存儲最優(yōu)路徑 bestP=cp; return bestP; if(cw+ai.w<=C)/進入左子樹 cw=cw+ai.w; cp=cp+ai.p; cxai.sign=1;/裝入背包 BackTrack(i+1); cw=cw-ai.w; cp=cp-ai.p;/回溯，進入右子樹 cxai.sign=0;/不裝入背包 BackTrack(i+1); return bestP;

13、int KnapSack3(int n,goods a,int C,int x) for(int i=0;i<n;i+) xi=0; ai.sign=i; sort(a,a+n,m);/將各物品按單位重量價值降序排列 BackTrack(0); return bestP; int main() goods bN; printf("物品種數(shù)n: "); scanf("%d",&n);/輸入物品種數(shù) printf("背包容量C: "); scanf("%d",&C);/輸入背包容量 for (in

14、t i=0;i<n;i+)/輸入物品i的重量w及其價值v printf("物品%d的重量w%d及其價值v%d: ",i+1,i+1,i+1); scanf("%d%d",&ai.w,&ai.p); bi=ai; int sum3=KnapSack3(n,a,C,X);/調(diào)用回溯法求0/1背包問題 printf("回溯法求解0/1背包問題:nX= "); for(i=0;i<n;i+) cout<<Xi<<" "/輸出所求Xn矩陣 printf("裝入總價

15、值%dn",sum3); for (i=0;i<n;i+) ai=bi; /恢復(fù)aN順序3）復(fù)雜度分析：最不理想的情況下，回溯法求解0/1背包問題的時間復(fù)雜度為：。由于其對蠻力法進行優(yōu)化后的算法，其復(fù)雜度一般比蠻力法要小。空間復(fù)雜度：有個物品，即最多遞歸層，存儲物品信息就是一個一維數(shù)組，即回溯法求解0/1背包問題的空間復(fù)雜度為。4.分支限界法求解背包問題：1）基本思想：分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，

16、或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當(dāng)前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當(dāng)前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當(dāng)右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當(dāng)擴展到葉節(jié)點時為問題的最優(yōu)值。2）代碼:#include<iostream>#include&

17、lt;algorithm>using namespace std;#define N 100/最多可能物體數(shù)struct goods/物品結(jié)構(gòu)體int sign;/物品序號int w;/物品重量int p;/物品價值aN;bool m(goods a,goods b)return (a.p/a.w)>(b.p/b.w);int max(int a,int b)return a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;struct KNAPNODE/狀態(tài)結(jié)構(gòu)體bool s1N; /當(dāng)前放入物體int k;/搜索深度int b;/價值

18、上界int w;/物體重量int p;/物體價值;struct HEAP/堆元素結(jié)構(gòu)體KNAPNODE *p;/結(jié)點數(shù)據(jù)int b; /所指結(jié)點的上界;/交換兩個堆元素void swap(HEAP &a, HEAP &b)HEAP temp = a;a = b;b = temp;/堆中元素上移void mov_up(HEAP H, int i)bool done = false;if(i!=1)while(!done && i!=1)if(Hi.b>Hi/2.b)swap(Hi, Hi/2);elsedone = true;i = i/2;/堆中元素下移v

19、oid mov_down(HEAP H, int n, int i)bool done = false;if(2*i)<=n)while(!done && (i = 2*i) <= n)if(i+1<=n && Hi+1.b > Hi.b)i+;if(Hi/2.b<Hi.b)swap(Hi/2, Hi);elsedone = true;/往堆中插入結(jié)點void insert(HEAP H, HEAP x, int &n)n+;Hn = x;mov_up(H,n);/刪除堆中結(jié)點void del(HEAP H, int &am

20、p;n, int i)HEAP x, y;x = Hi; y = Hn;n -;if(i<=n)Hi = y;if(y.b>=x.b)mov_up(H,i);elsemov_down(H, n, i);/獲得堆頂元素并刪除HEAP del_top(HEAP H, int &n)HEAP x = H1;del(H, n, 1);return x;/計算分支節(jié)點的上界void bound( KNAPNODE* node, int M, goods a, int n)int i = node->k;float w = node->w;float p = node-&g

21、t;p;if(node->w>M) / 物體重量超過背包載重量node->b = 0; / 上界置為0elsewhile(w+ai.w<=M)&&(i<n) w += ai.w; / 計算背包已裝入載重p += ai+.p; / 計算背包已裝入價值if(i<n)node->b = p + (M - w)*ai.p/ai.w;elsenode -> b = p;/用分支限界法實現(xiàn)0/1背包問題int KnapSack4(int n,goods a,int C, int X)int i, k = 0; / 堆中元素個數(shù)的計數(shù)器初始化為

22、0int v;KNAPNODE *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; / 分配堆的存儲空間for( i=0; i<n; i+)ai.sign=i; /記錄物體的初始編號sort(a,a+n,m); / 對物體按照價值重量比排序xnode = new KNAPNODE; / 建立父親結(jié)點for( i=0; i<n; i+) / 初始化結(jié)點xnode->s1i = false;xnode->k = xnode->w = xnode->p = 0;while(xnode->

23、;k<n) ynode = new KNAPNODE; / 建立結(jié)點y*ynode = *xnode; /結(jié)點x的數(shù)據(jù)復(fù)制到結(jié)點yynode->s1ynode->k = true; / 裝入第k個物體ynode->w += aynode->k.w; / 背包中物體重量累計ynode->p += aynode->k.p; / 背包中物體價值累計ynode->k +; / 搜索深度+bound(ynode, C, a, n); / 計算結(jié)點y的上界y.b = ynode->b;y.p = ynode;insert(heap, y, k); /結(jié)

24、點y按上界的值插入堆中znode = new KNAPNODE; / 建立結(jié)點z*znode = *xnode; /結(jié)點x的數(shù)據(jù)復(fù)制到結(jié)點zznode->k+; / 搜索深度+bound(znode, C, a, n); /計算節(jié)點z的上界z.b = znode->b;z.p = znode;insert(heap, z, k); /結(jié)點z按上界的值插入堆中delete xnode;x = del_top(heap, k); /獲得堆頂元素作為新的父親結(jié)點xnode = x.p;v = xnode->p;for( i=0; i<n; i+) /取裝入背包中物體在排序前的序號if(xnode->s1i)Xai.sign =1 ;elseXai.sign = 0;delete xnode;delete heap;return v; /返回背包中物體的價值/*測試以上算法的主函數(shù)*/int main()goods bN;printf("物品種數(shù)n: &qu