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

1、一、實驗內(nèi)容：分別用蠻力法、動態(tài)規(guī)劃法、回溯法和分支限界法求解 0/1 背包問題。注：0/1背包問題：給定n種物品和一個容量為C的背包，物品i的重量是 wi，其價值為vi，背包問題是如何使選擇裝入背包內(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 X

3、N,cxN;/* 蠻力法求解 0/1 背包問題 */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)

4、 Force(0);return bestP;int main()goods bN;printf(" 物品種數(shù) n: "); scanf("%d",&n);/ 輸入物品種數(shù) printf(" 背包容量 C: ");3 / 22sea nf("%d", &C);輸入背包容量for (int i=0;i<n;i+)輸入物品i的重量w及其價值vprintf("物品 %d 的重量 w%d及其價值 v%d:",i+1,i+1,i+1);sea nf("%d%d",

5、&ai.w,&ai.p);bi=ai;int sum仁KnapSack1(n,a,C,X);調(diào)用蠻力法求0/1背包問題printf(”蠻力法求 解0/1背包問題:nX=");for(i=0;i <n ;i+)coutv<Xivv" "/ 輸出所求 Xn矩陣printf("裝入總價值 %dn",sum1);bestP=0,cp=0,cw=0;/恢 恢復(fù)初始化3)復(fù)雜度分析：蠻力法求解0/1背包問題的時間復(fù)雜度為：T(n) 0(2n)。2動態(tài)規(guī)劃法求解0/1背包問題：1) 基本思想：令V(i,j)表示在前i(1 in)個

6、物品中能夠裝入容量為j(1 j C)的背包中的物品的最大值，則可以得到如下動態(tài)函數(shù)：V(i,0) V(0,j) 0V(i 1,j)(j wmaxV(i 1,j),V(i1,j w) v(j w)iii按照下述方法來劃分階段：第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；以此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。2) 代碼：#in clude<iostream>#in clude<algorithm>using n amesp

7、ace std;#define N 100最多可能物體數(shù)struct goods/物品結(jié)構(gòu)體int sig n;物品序號int w;物品重量int p;物品價值aN;bool m(goods a,goods b)retur n (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;int KnapSack2(int n,goods a,int C,int x)int VN10*N;for(int i=0;i<=n;i+)/ 初始化第 0 列Vi0=

8、0;for(int j=O;jv二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;elseVij=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(" 物品種

9、數(shù) n: ");scanf("%d",&n); / 輸入物品種數(shù)printf(" 背包容量 C: ");scanf("%d",&C); / 輸入背包容量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ī)劃法

10、求0/1背包問題printf("動態(tài)規(guī)劃法求解0/1背包問題:nX=");for(i=0;i <n ;i+)coutv<Xivv" "/ 輸出所求 Xn矩陣printf("裝入總價值 dn",sum2);for (i=0;i <n ;i+)ai=bi;/恢復(fù)aN順序3) 復(fù)雜度分析：動態(tài)規(guī)劃法求解0/1背包問題的時間復(fù)雜度為：T(n) O(n C)。3回溯法求解0/1背包問題：1) 基本思想：回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用 限界函數(shù)(bounding function)來處死那些實際

11、上不可能產(chǎn)生所需解的活結(jié)點，以 減少問題的計算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。對于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1向量組 成，可用子集數(shù)表示。在搜索解空間樹時，只要其左兒子結(jié)點是一個可行結(jié)點， 搜索就進入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時就進入右子樹搜索。2) 代碼：#in clude<iostream>#include<algorithm>using namespace std;#define N 100/ 最多可能物體數(shù) struct goods / 物品結(jié)構(gòu)體int sign;/ 物品序號int w;/ 物品重量int

12、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;int BackTrack(int i)9 / 223.曰 e+cbucbM 曰 e+MoHMoWRWV®、xov/vv 曰 e+Mg 七 宀CL4S q una) 宀-cbHCRS q型蚩sw迴>注Ex。"蘭 X(+KUVKO艾莖一)O4McbvcRS q)七)(LUC_=一7Z 一 OLax

13、 4U-O4ur=e spooqu luDcoMoesdeuy 4£ 宀CL4S q una)二 土) MoeEoeH*<<kuo''u6_s.曰 ex。宀 w中柜<®冕回注d.曰ecbucbM 曰 eMoHMo 二 土) MoeEoeH*<<FL"U6_S.曰 ex。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("

14、物品種數(shù) n: ");scanf("%d",&n);/ 輸入物品種數(shù)printf(" 背包容量 C: ");sea nf("%d", &C);輸入背包容量for (int i=0;i<n;i+)輸入物品i的重量w及其價值vprintf("物品%d的重量w%d及其價值v%d:",i+1,i+1,i+1);seanf("%d%d",&ai.w,&ai.p);bi=ai;int sum3=KnapSack3(n,a,C,X);調(diào)用回溯法求0/1背包問題p

15、rintf(”回溯法求解0/1背包問題:nX=");for(i=0;i <n ;i+)coutv<Xivv" "/ 輸出所求 Xn矩陣printf("裝入總價值 %dn",sum3);for (i=0;i <n ;i+)ai=bi;/恢復(fù)aN順序3)復(fù)雜度分析：最不理想的情況下，回溯法求解0/1背包問題的時間復(fù)雜度為：T(n) 0(2 n)。由于其對蠻力法進行優(yōu)化后的算法，其復(fù)雜度一般比蠻力法要 小?？臻g復(fù)雜度：有n個物品，即最多遞歸n層，存儲物品信息就是一個一維 數(shù)組，即回溯法求解0/1背包問題的空間復(fù)雜度為 0(n)。4分

16、支限界法求解背包問題：1)基本思想：分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算法。一 般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解 空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條 件的一個解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達到極大或極 小的解，即在某種意義下的最優(yōu)解。首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進 行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值 加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查當(dāng)前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點

17、是 可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當(dāng)前擴展結(jié)點的右兒子 結(jié)點一定是可行結(jié)點，僅當(dāng)右兒子結(jié)點滿足上界約束時才將它加入子集樹和活 結(jié)點優(yōu)先隊列。當(dāng)擴展到葉節(jié)點時為問題的最優(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

18、.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; / 價值上界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;/

19、 堆中元素上移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;/ 堆中元素下移void 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 > H

20、i.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 &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, i

21、nt &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->p;if(node->w>M) / 物體重量超過背包載重量 node->b = 0; / 上界置為 0else while(w+ai.w<=M)&&(i<n)w += ai.w; / 計算背包已裝入載重p += ai+.p;

22、 / 計算背包已裝入價值 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ù)器初始化為 0int v;KNAPNODE *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; / 分配堆的存儲空間for( i=0; i<n; i+)ai.sign=i; / 記錄物體的初始編

23、號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->k<n) ynode = new KNAPNODE;/ 建立結(jié)點 y*ynode = *xnode;/ 結(jié)點 x 的數(shù)據(jù)復(fù)制到結(jié)點yynode->s1ynode->k = true;/ 裝入第 k 個物體 ynode->w += ay

24、node->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é)點 y 按上界的值插入堆中 znode = newKNAPNODE; / 建立結(jié)點 z*znode = *xnode; / 結(jié)點 x 的數(shù)據(jù)復(fù)制到結(jié)點 zznode->k+;/ 搜索深度 +bound(znode, C, a, n); /

25、計算節(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: