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

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

2、結(jié)點(diǎn)，記錄 每次得到的裝入總價(jià)值，然后記錄遍歷過的最大價(jià)值。2）代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數(shù)struct goods 物品結(jié)構(gòu)體(int sign; 物品序號(hào)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 ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;/*蠻力法求

3、解0/1背包問題*/int Force(int i)(if(in-1)(if(bestPcpcw+ai.w=C)for (int k=0;kk+) Xk=cxk;/ 存儲(chǔ)最優(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()(goo

4、ds bN;printf(物品種數(shù) n:);scanf(%d, 輸入物品種數(shù)printf(背包容量 C:);scanf(%d, /輸入背包容量for (int i=0;ii +) 輸入物品i的重量w及其價(jià)值v(printf(-物品%d的重量w%d及其價(jià)值v%d:,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;ii + +)coutXi ;/輸出所求Xn矩陣printf(裝入總價(jià)值%dn,sum1);be

5、stP=0,cp=0,cw=0;/ 恢復(fù)初始化)復(fù)雜度分析：蠻力法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n) O(2n)。動(dòng)態(tài)規(guī)劃法求解0/1背包問題：基本思想：令V(i,j)表示在前i(1 i n)個(gè)物品中能夠裝入容量為j(1 j C)的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)函數(shù)：V(i,0) V(0,j) 0V(i 1,j)(j wi) V(i,j) V(i 1,j),V(i 1,j wi) vi (j wi) max按照下述方法來劃分階段：第一階段，只裝入前1個(gè)物品，確定 在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2 個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；以此

6、類推，直到 第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取 得的最大價(jià)值。代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數(shù)struct goods( 物品結(jié)構(gòu)體int sign; /物品序號(hào)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 ab?b:a;)int n,C,bestP=0,cp=0,cw=0;

7、int XN,cxN;int KnapSack2(int n,goods a,int C,int x)(int VN10*N; for(int i=0;ii + +) Vi=0; for(int j=0;jj +) Vj=0; for(i = 1;ii + +) for(j = 1;jj +) 初始化第0列初始化第0行計(jì)算第i 行，進(jìn)行第i次迭代if(jai-1.w) Vij=Vi-1j; else Vij = max(Vi-1j,Vi-1j-ai- 1.w+ai-1.p); j=C; 求裝入背包的物品 for (i=n;ii-) ( if (VijVi- 1j)( xi-1 = 1; j=j

8、-ai-1.w; xi-1=0; else return VnC; /返回背包 取得的最大價(jià)值int main()(goods bN;printf(物品種數(shù) n: ”)；scanf(%d, 輸入物品種數(shù) printf(背包容量 C: ); scanf(%d, / 輸入背包容量for (int i=0;ii +) /輸入物品i的重量w及其價(jià)值v ( printf(-物品 %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)用動(dòng)態(tài)規(guī)劃法求0/1背包問題 prin

9、tf(-動(dòng)態(tài)規(guī)劃法求解0/1背包問題:nX=);for(i=0;ii + +) coutXi ;/輸出所求 Xn矩陣 printf(裝入總價(jià) 值%dn,sum2); for (i=0;ii +) ( ai = bi; /恢復(fù) aN順序)3)復(fù)雜度分析：動(dòng)態(tài)規(guī)劃法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n) O(n C)?；厮莘ㄇ蠼?/1背包問題：1)基本思想：回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不 斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn) 生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。這種具有限界函數(shù)的深度 優(yōu)先生成法稱為回溯法。對(duì)于有n種可選物品

10、的0/1背包問題，其解空間由長度為n的 0-1向量組成，可用子集數(shù)表示。在搜索解空間樹時(shí)，只要其左兒子結(jié) 點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解 時(shí)就進(jìn)入右子樹搜索。2)代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數(shù)struct goods 物品結(jié)構(gòu)體(int sign; 物品序號(hào)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,i

11、nt b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;int BackTrack(int i)(if(in-1)( if(bestPcp)( for (int k=0;kk+) bestP=cp; Xk=cxk;/ 存 儲(chǔ)最優(yōu)路徑 return bestP; /進(jìn)入左子樹 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; 回溯，進(jìn)入右子樹cxai.sign=0; 不裝入背包Back

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

13、f(-物品%d的重量w%d及其價(jià)值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;ii + +) coutXi ;/輸出所求 Xn矩陣 printf(裝入總價(jià)值%dn,sum3); for (i=0;ii + +) ai=bi; 恢復(fù) aN順序復(fù)雜度分析：最不理想的情況下，回溯法求解0/1背包問題的時(shí)間復(fù)雜度為:T(n) O(2n)。由于其對(duì)蠻力法進(jìn)行優(yōu)化后的算法，其復(fù)雜度一般比 蠻力法

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

15、袋的 物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(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)值。2）代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數(shù)struct goods 物品結(jié)構(gòu)體(int sign; 物品序號(hào)int w; 物品重量int p; /物品價(jià)值)a

16、N；bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);)int max(int a,int b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;struct *E /狀態(tài)結(jié)構(gòu)體(bool s1N; 當(dāng)前放入物體int k; 搜索深度int b; 價(jià)值上界int w; /物體重量int p; /物體價(jià)值;struct HEAP /堆元素結(jié)構(gòu)體(*E *p;/結(jié)點(diǎn)數(shù)據(jù)int b; 所指結(jié)點(diǎn)的上界;交換兩個(gè)堆元素void swap(HEAP a, HEAP b)(HEAP temp = a;a

17、 = b;b = temp;)堆中元素上移void mov_up(HEAP H, int i)(bool done = false;if(i! = 1)while(!done i! = 1)if(Hi.bHi/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 Hi.b)i+；)if(Hi/2.bHi.b)(swap(Hi/2,

18、 Hi);)else(done = true;)往堆中插入結(jié)點(diǎn)void insert(HEAP H, HEAP x, int n) ( n + + ;Hn = 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 = n)(Hi = y;if(y.b=x.b)(mov_up(H,i);)else(mov_down(H, n, i);)獲得堆頂元素并刪除HEAP del_top(HEAP H, int n)(HEAP x = H;del(H, n, 1);return x;)計(jì)算

19、分支節(jié)點(diǎn)的上界void bound( *E* node, int M, goods a, int n)(int i = nodefloat w = nodefloat p = node-if(node-wM)( /物體重量超過背包載重量node-b = 0; /上界置為0)else(while(w+ai.w=M)(in)(w += ai.w; /計(jì)算背包已裝入載重p += ai + +.p; /計(jì)算背包已裝入價(jià)值)if(in)(node-b = p + (M - w)*ai.p/ai.w;)else(node - b = p;)用分支限界法實(shí)現(xiàn)0/1背包問題int KnapSack4(int

20、n,goods a,int C, int X)(int i, k = 0; /堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0int v;*E *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; /分配堆的存儲(chǔ)空間for( i=0; i i +)(ai.sign=i; /記錄物體的初始編號(hào))sort(a,a + n,m); /對(duì)物體按照價(jià)值重量比排序 xnode = new *E; / 建立父親結(jié)點(diǎn) for( i=0; i i +)( / 初始化結(jié)點(diǎn)xnode-s1i = false;)xnode-k = xnode-w = xnode-

21、p = 0;while(xnode-kn) (ynode = new *E; / 建立結(jié)點(diǎn) y*ynode = *xnode; /結(jié)點(diǎn)x的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)y ynode-s1ynode-k = true; / 裝入第 k 個(gè)物體 ynode-w += aynode-k.w; /背包中物體重量累計(jì) ynode-p += aynode-k.p; /背包中物體價(jià)值累計(jì) ynode-k + + ; / 搜索深度+ +bound(ynode, C, a, n); / 計(jì)算結(jié)點(diǎn) y 的上界 y.b = ynode-y.p = ynode;insert(heap, y, k); /結(jié)點(diǎn)y按上界的值插入堆中zn

22、ode = new *E; / 建立結(jié)點(diǎn) z*znode = *xnode; /結(jié)點(diǎn)x的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)z znode- /搜索深度+ +bound(znode, C, a, n); 計(jì)算節(jié)點(diǎn)z的上界z.b = znode-z.p = znode;insert(heap,乙k); /結(jié)點(diǎn)z按上界的值插入堆中 delete xnode;x = del_top(heap, k); 獲得堆頂元素作為新的父親結(jié)點(diǎn) xnode = x.p;)v = xnode-for( i=0; i i +)( /取裝入背包中物體在排序前的序號(hào) if(xnode-s1i)(Xai.sign =1 ;)else(Xai.sign = 0;)delete xnode;delete heap;return v;