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

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

2、碼：#include#includeusing namespace std;#define N 100 /最多可能物體數(shù)struct goods /物品結(jié)構(gòu)體(int sign; /物品序號int w; 物品重量int p; 物品價(jià)值aN;bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);int max(int a,int b)(return an-1)if(bestPcp&cw+ai.w=C)for (int k=0;kn;k+)Xk=cxk;/存儲最優(yōu)路徑bestP=cp;return bestP;cw=cw+ai.w;cp=cp+ai.p

3、;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()(goods bN;printf(物品種數(shù) n:);scanf(%d”,&n);/輸入物品種數(shù)printf (-背包容量 C:);scanf(d,&C);輸入背包容量for (int i=0;in;i+) /輸入物品i的重量w及其價(jià)值v(printf(-物品d的重量 w%d及其價(jià)值 v%d:

4、 ，i+1,i+1,i+1);scanf(d%d,&ai.w,&ai.p);bi=ai;int sum1=KnapSack1(n,a,C,X);/調(diào)用蠻力法求 0/1 背包問題printf (-蠻力法求解0/1背包問題：nX= )；for(i=0;in;i+)coutXi ;/輸出所求 Xn矩陣printf(裝入總價(jià)值 %dn,sum1);bestP=0,cp=0,cw=0;/恢復(fù)初始化復(fù)雜度分析：蠻力法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n) O(2n)。動態(tài)規(guī)劃法求解0/1背包問題：基本思想：令V(i,j)表示在前i(1 i n)個(gè)物品中能夠裝入容量為j(1 j w )i ii按照下述方

5、法來劃分階段：第一階段，只裝入前1個(gè)物品，確定在 各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品， 確定在各種情況下的背包能夠得到的最大價(jià)值；以此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最 if(jai-1.w)大價(jià)值。2)代碼：#include #include using namespace #define N 100 struct goods intint大價(jià)值。2)代碼：#include #include using namespace #define N 100 struct goods intintint aN; bool

6、m(goods a,goods b) return (a.p/a.w)(b.p/b.w); int std;最多可能物體數(shù)/物品結(jié)構(gòu)體sign;w; 物品重量p; 物品價(jià)值/物品序號max(int a,int b)return ab?b:a;int int int n,C,bestP=0,cp=0,cw=0;return ab?b:a;int int int n,C,bestP=0,cp=0,cw=0;XN,cxN;KnapSack2(int n,goodsa,int C,int x)int VN10*N;for(int i=0;i=n;i+)Vi0=0;for(int j=0;j=C;j+)

7、int VN10*N;for(int i=0;i=n;i+)Vi0=0;for(int j=0;j=C;j+)V0j=0;for(i=1;i=n;i+)for(j=1;j0;i-) if (VijVi-1j) xi-1=1; j=j-ai-1.w;else xi-1=0;return VnC; /返回背包取得的最大價(jià)值int main()goods bN;printf(物品種數(shù) n:);scanf(%d”,&n); /輸入物品種數(shù)printf (-背包容量 C:);scanf(d，&C); /輸入背包容量for (int i=0;in;i+) /輸入物品i的重量w及其價(jià)值vprintf (-物

8、品d 的重量 w%d及其價(jià)值 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;in;i+)coutXi ;/輸出所求 Xn矩陣 printf(裝入總價(jià)值 %dn”,sum2);for (i=0;in;i+) ai=bi;/恢復(fù)aN順序3)復(fù)雜度分析：動態(tài)規(guī)劃法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n) = O(nxC)。回溯法求解0/1背包問題：基本思想：回溯法：為了避免生成那些不

9、可能產(chǎn)生最佳解的問題狀態(tài)，要不斷 地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所 需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。這種具有限界函數(shù)的深度優(yōu)先生 成法稱為回溯法。對于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1 向量組成，可用子集數(shù)表示。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一 個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)就進(jìn) 入右子樹搜索。代碼：#include#includeusing namespace std;#define N 100/最多可能物體數(shù)struct goods /物品結(jié)構(gòu)體int sign; /物品序號int

10、w;/物品重量int p;/物品價(jià)值aN;bool m(goods a,goods b)return (a.p/a.w)(b.p/b.w);int max(int a,int b)return an-1)if(bestPcp)for (int k=0;kn;k+)Xk=cxk;/存儲最優(yōu)路徑bestP=cp;return bestP;if(cw+ai.w=C)/進(jìn)入左子樹cw=cw+ai.w;cp=cp+ai.p;cxai.sign=1; /裝入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.p;/回溯，進(jìn)入右子樹cxai.sign=0; /不裝入背包BackTrac

11、k(i+1);return bestP;int KnapSack3(int n,goods a,int C,int x)for(int i=0;in;i+)xi=0;ai.sign=i;sort(a,a+n,m);/各物品按單位重量價(jià)值降序排列BackTrack(0);return bestP;int main()goods bN;printf(物品種數(shù) n:);scanf(%d”,&n); /輸入物品種數(shù)printf (-背包容量 C:);scanf(d，&C); /輸入背包容量for (int i=0;in;i+)/輸入物品i的重量w及其價(jià)值vprintf (-物品d 的重量 w%d及其價(jià)

12、值 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;in;i+)coutXi ;/輸出所求 Xn矩陣printf(裝入總價(jià)值 dn”,sum3);for (i=0;in;i+)ai=bi;/恢復(fù)aN順序復(fù)雜度分析：最不理想的情況下，回溯法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n) O(2n)。由于其對蠻力法進(jìn)行優(yōu)化后的算法，其復(fù)雜度一般比蠻力法要小?？臻g復(fù)雜度：有n個(gè)物品，即最多遞歸n層

13、，存儲物品信息就是一個(gè)一維數(shù)組，即回溯法求解0/1背包問題的空間復(fù)雜度為O(n)。分支限界法求解背包問題：基本思想：分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的算 法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼?目標(biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo) 則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某 一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大 到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級由已裝袋的物 品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿

14、剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子 結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展 結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才 將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。代碼：#include#includeusing namespace std;#define N 100 /最多可能物體數(shù)struct goods /物品結(jié)構(gòu)體(int sign; /物品序號int w; 物品重量int p; 物品價(jià)值aN;bool m(goods a,goods b)(return (a.p/a.w)(b.p

15、/b.w);int max(int a,int b)(return aHi/2.b) swap(Hi, Hi/2); else( done = 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 Hi.b) i+;if(Hi/2.bHi.b) swap(Hi/2, Hi);else( done = true;/往堆中插入結(jié)點(diǎn)void insert(HEAP H, HEAP x, int &n)(n+;Hn

16、 = x;mov_up(H,n);/刪除堆中結(jié)點(diǎn)void del(HEAP H, int &n, int i)(HEAP x, y;x = Hi; y = Hn;n -;if(i=x.b)(mov_up(H,i);else(mov_down(H, n, i);/獲得堆頂元素并刪除HEAP del_top(HEAP H, int &n)(HEAP x = H1;del(H, n, 1);return x;/計(jì)算分支節(jié)點(diǎn)的上界void bound( KNAPNODE* node, int M, goods a, int n)(int i = node-k;float w = node-w;floa

17、t p = node-p;if(node-wM)( /物體重量超過背包載重量node-b = 0;/ 上界置為 0else(while(w+ai.w=M)&(in)w += ai.w;/計(jì)算背包已裝入載重p += ai+.p; /計(jì)算背包已裝入價(jià)值if(ib = p + (M - w)*ai.p/ai.w;else(node - b = p;用分支限界法實(shí)現(xiàn)0/1背包問題int KnapSack4(int n,goods a,int C, int X)(/堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0int i, k = 0;/堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0int v;KNAPNODE *xnode, *yn

18、ode, *znode;HEAP x, y, z, *heap;/分配堆的存儲空間heap = new HEAPn*n;/分配堆的存儲空間for( i=0; in; i+)(記錄物體的初始編號ai.sign=i;記錄物體的初始編號/對物體按照價(jià)值重量比排序/建立父親結(jié)點(diǎn)/對物體按照價(jià)值重量比排序/建立父親結(jié)點(diǎn)/ 初始化結(jié)點(diǎn)xnode = new KNAPNODE;for( i=0; is1i = false;xnode-k = xnode-w = xnode-p = 0;while(xnode-ks1ynode-k= true;.w;ynode-p += aynode-k.p;/ynode-k

19、 +;/bound(ynode, C, a, n);/y.b = ynode-b;y.p = ynode;結(jié)點(diǎn)y結(jié)點(diǎn)y按上界的值插入堆中/建立結(jié)點(diǎn)z結(jié)點(diǎn)X的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)z/搜索深度+計(jì)算節(jié)點(diǎn)z的上界znode = new KNAPNODE;*znode = *xnode;znode-k+;bound(znode, C, a, n);z.b = znode-b;z.p = znode;結(jié)點(diǎn)z結(jié)點(diǎn)z按上界的值插入堆中delete xnode;獲得堆頂元素作為新的父親結(jié)點(diǎn)x = del_top(heap, k);獲得堆頂元素作為新的父親結(jié)點(diǎn)xnode = x.p;v = xnode-p;for( i=0; is1i)Xai.sign =1 ;else(Xai.sign = 0;delete xnode;delete heap;return v;返回背包中物體的價(jià)值/*測試以上算法的主函數(shù)*/int main()(goods bN;printf(物品種數(shù) n:);scanf(%d”,&n); /輸入物品種數(shù)printf (-背包容量 C:);s