回溯法求0-1背包問題

1、1學(xué)號:日 期:算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告姓名：_得 分：、實(shí)驗(yàn)內(nèi)容：用回溯法求解0/1背包問題注：給定n種物品和一個(gè)容量為C的背包，物品i的重量是Wj，其價(jià)值為V，背包問題是如何使選擇裝入背包內(nèi)的物品，使得裝入背包中的物品的總價(jià)值最大。其中，每種物品只有全部裝入背包或不裝入背包兩種選擇。、所用算法的基本思想及復(fù)雜度分析：1. 回溯法求解背包問題：1) 基本思想：回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷 地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。這種具有限界函數(shù)的深度優(yōu)先生 成法稱為回溯法。對于有n種可選物品

2、的0/1背包問題，其解空間由長度為n的0-1 向量組成，可用子集數(shù)表示。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一 個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)就進(jìn) 入右子樹搜索。2) 復(fù)雜度分析：回溯法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n)=0(2n)?？臻g復(fù)雜度：有n個(gè)物品，即最多遞歸n層，存儲物品信息就是一個(gè)一維數(shù)組，即回溯法求解0/1背包問題的空間復(fù)雜度為O(n) o2. 以動態(tài)規(guī)劃法驗(yàn)證：1)基本思想：令V(i, j)表示在前i(1幻乞n)個(gè)物品中能夠裝入容量為j(1乞j < C)的背包中的物品的最大值，則可以得到如下動態(tài)函數(shù)：V(i,0) =V(O,j) =0如

3、)牛，jjw).maxV(i-1,j),V(i -1, j-Wi)+v,(j ZwJ按照下述方法來劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值； 第二階段，只裝入前2個(gè)物品,確定在各種情況下的背包能夠得到的最大價(jià)值；以此類推，直到第 n個(gè) 階段。最后，Vn,C）便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。O(n C)。2)復(fù)雜度分析：動態(tài)規(guī)劃法求解0/1背包問題的時(shí)間復(fù)雜度為：T(n)三、源程序及注釋：#in clude<iostream>#i nclude<algorithm>using n amespace std;stru

4、ct goods/物品結(jié)構(gòu)體int sign;/物品序號int w;/物品重量int v;/物品價(jià)值a100;bool m(goods a,goods b)return (a.v/a.w)>(b.v/b.w);int max(i nt a,i nt b)retur n a<b?b:a;int n, C,bestP=0,cp=0,cw=0;int x100,cx100;/回溯法函數(shù)int BackTrack(i nt i)if(i> n-1)if(bestP<cp)for (int k=0;k< n; k+)xk=cxk;存儲最優(yōu)路徑bestP=cp;return

5、bestP;if(cw+ai.w<=C)/ 進(jìn)入左子樹cw=cw+ai.w;cp=cp+ai.v;cxai.sign=1;/ 裝入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.v;/回溯，進(jìn)入右子樹/不裝入背包 cxai.sig n=0; BackTrack(i+1); return bestP;/回溯法求解0/1背包問題int Kn apSack( int n,goods a,i nt C,i nt x)for(i nt i=0;i< n; i+)xi=0;ai.sig n=i;sort(a,a+n,m);將各物品按單位重量價(jià)值降序排列BackTrac

6、k(0);return bestP;/動態(tài)規(guī)劃法求解0/1背包問題int Kn apSack1( int n,goods a,i nt C,i nt x)/初始化第0列/初始化第0行/計(jì)算第i行，進(jìn)行第i次迭代int V1001000;for(i nt i=0;i<=n ;i+)Vi0=0;for(i nt j=0;j<=C;j+)V0j=0;for(i=1;i<=n ;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.v);j=C; /求裝入背包的物品fo

7、r (i=n; i>0;i-)if (Vij>Vi-1j)xi-1=1;j=j-ai-1.w;else xi-1=0; return Vn C; /返回背包取得的最大價(jià)值/測試以上算法的主函數(shù)int mai n()printf(”物品種數(shù) n:");scan f("%d", &n); /輸入物品種數(shù)printf("背包容量 C:");scan f("%d", &C); /輸入背包容量for (i nt i=0;i <n ;i+)/輸入物品i的重量w及其價(jià)值v6#printf(" 物

8、品 d的重量 w%d及其價(jià)值 v%d: ",i+1,i+1,i+1); scan f("%d%d",&ai.w,&ai.v);int sum1=K napSack1( 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矩陣printf("裝入總價(jià)值 %dn",sum1);int sum2=K napSack (n ,a,C,x

9、);printf("回溯法求解0/1背包問題:nX=");for(i=0;i <n ;i+)cout<<xi<<" "/輸出所求 Xn矩陣printf("裝入總價(jià)值 %dn",sum2);return 0;四、運(yùn)行輸出結(jié)果:IK180品1旳重量譏1及戶一L L U 1 J不八心回溯法求解恥瓚頤題： fi=t 181 j價(jià)值圳©Press any Sce to continueGO相同的數(shù)據(jù)，求相同同的問題，用不同的方法，得到的結(jié)果，所得結(jié)果 正是所求問題的最優(yōu)解，以動態(tài)規(guī)劃法驗(yàn)證回溯法求解的 0/1背包問題是正 確的。五、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題、采取的措施及獲得的相關(guān)經(jīng)驗(yàn)教訓(xùn)：1. 本實(shí)驗(yàn)中用回溯法求0/1背包問題，課本上給出的算法偽代碼只能求出背包裝入物品的最大總價(jià)值，所以我在對物品構(gòu)造結(jié)構(gòu)體時(shí)定義了一個(gè)int型變量 sign ,用來記錄所給物品的原始順序，并在適當(dāng)位置記錄裝入和不裝入背包，存儲求解路徑，從而求出原始問題的解向量 X。2. 在本實(shí)驗(yàn)中，本為增強(qiáng)回溯法求解 0/1背包問題函數(shù)的可移植性，