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

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

2、的最大價(jià)值。2）代碼:#include<iostream>#include<algorithm>using 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 a<b?b:a;int n,C,bestP=0,cp=0,cw=0;int XN,cxN;/*蠻力法求解0/1背包問(wèn)題

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;/存儲(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(

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

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

6、各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；以此類(lèi)推，直到第個(gè)階段。最后，便是在容量為的背包中裝入個(gè)物品時(shí)取得的最大價(jià)值。 2）代碼： #include<iostream> #include<algorithm> using 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)>(

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+)/計(jì)算第i行，進(jìn)行第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;/返回背包取得的最大價(jià)值 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及其價(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背包問(wèn)題 printf("動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題:nX= "); for(i=0;i<n;i+) cout<<Xi<<" "/輸出所求Xn矩陣 print

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

11、左子樹(shù)。當(dāng)右子樹(shù)中有可能包含最優(yōu)解時(shí)就進(jìn)入右子樹(shù)搜索。 2）代碼: #include<iostream> #include<algorithm> using 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 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;/存儲(chǔ)最優(yōu)路徑 bestP=cp; return bestP; if(cw+ai.w<=C)/進(jìn)入左子樹(shù) cw=cw+ai.w; cp=cp+ai.p; cxai.sign=1;/裝入背包 BackTrack(i+1); cw=cw-ai.w; cp=cp-ai.p;/回溯，進(jìn)入右子樹(shù) 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);/將各物品按單位重量?jī)r(jià)值降序排列 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及其價(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 sum3=KnapSack3(n,a,C,X);/調(diào)用回溯法求0/1背包問(wèn)題 printf("回溯法求解0/1背包問(wèn)題:nX= "); for(i=0;i<n;i+) cout<<Xi<<" "/輸出所求Xn矩陣 printf("裝入總價(jià)

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

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

17、lt;algorithm>using 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 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;/價(jià)值

18、上界int w;/物體重量int p;/物體價(jià)值;struct HEAP/堆元素結(jié)構(gòu)體KNAPNODE *p;/結(jié)點(diǎn)數(shù)據(jù)int b; /所指結(jié)點(diǎn)的上界;/交換兩個(gè)堆元素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é)點(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 &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;/計(jì)算分支節(jié)點(diǎn)的上界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) / 物體重量超過(guò)背包載重量node->b = 0; / 上界置為0elsewhile(w+ai.w<=M)&&(i<n) w += ai.w; / 計(jì)算背包已裝入載重p += ai+.p; / 計(jì)算背包已裝入價(jià)值if(i<n)node->b = p + (M - w)*ai.p/ai.w;elsenode -> b = p;/用分支限界法實(shí)現(xiàn)0/1背包問(wèn)題int KnapSack4(int n,goods a,int C, int X)int i, k = 0; / 堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為

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

23、;k<n) ynode = new KNAPNODE; / 建立結(jié)點(diǎn)y*ynode = *xnode; /結(jié)點(diǎn)x的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)yynode->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->b;y.p = ynode;insert(heap, y, k); /結(jié)

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