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

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

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

4、ct goods/物品結構體int sign;/物品序號int w;/物品重量int v;/物品價值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;/回溯法函數int BackTrack(i nt i)if(i> n-1)if(bestP<cp)for (int k=0;k< n; k+)xk=cxk;存儲最優路徑bestP=cp;return

5、bestP;if(cw+ai.w<=C)/ 進入左子樹cw=cw+ai.w;cp=cp+ai.v;cxai.sign=1;/ 裝入背包BackTrack(i+1);cw=cw-ai.w;cp=cp-ai.v;/回溯，進入右子樹/不裝入背包 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);將各物品按單位重量價值降序排列BackTrac

6、k(0);return bestP;/動態規劃法求解0/1背包問題int Kn apSack1( int n,goods a,i nt C,i nt x)/初始化第0列/初始化第0行/計算第i行，進行第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; /返回背包取得的最大價值/測試以上算法的主函數int mai n()printf(”物品種數 n:");scan f("%d", &n); /輸入物品種數printf("背包容量 C:");scan f("%d", &C); /輸入背包容量for (i nt i=0;i <n ;i+)/輸入物品i的重量w及其價值v6#printf(" 物

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