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

2、子集數(shù)表示。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入左子樹。當右子樹中有可能包含最優(yōu)解時就進入右子樹搜索。2)復雜度分析：回溯法求解0/背1包問題的時間復雜度為：T(n)O(2n)?？臻g復雜度：有n個物品，即最多遞歸n層，存儲物品信息就是一個一維數(shù)組，即回溯法求解0/背1包問題的空間復雜度為O(n)。2.以動態(tài)規(guī)劃法驗證：1)基本思想：令V(i,j)表示在前i(1in)個物品中能夠裝入容量為j(1jC)的背包中的物品的最大值，則可以得到如下動態(tài)函數(shù)：V(i,0)V(0,j)0JV(i1,j)(jw)iii按照下述方法來劃分階段：第一階段，只裝入前1個物品，確定在各種情況下的

3、背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；以此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。2)復雜度分析：動態(tài)規(guī)劃法求解背包問題的時間復雜度為：T(n)二O(nC)。三、源程序及注釋：物品結構體物品序號物品重量/物;品價值物回溯法函數(shù)存儲最優(yōu)路徑進入左子樹裝入背包回溯，進入右子樹不裝入背包回/溯法求解0/背1包問題將各物品按單位重量價值降序排列/動態(tài)規(guī)劃法求解0/背1包問題初始化第列初始化第行計算第行，進行第次迭代求裝入背包的物品返回背包取得的最大價值測試以上算法的主函數(shù)物品種數(shù) :紡品m的重量

4、w31及其血點暢態(tài)規(guī)劃法求解恥償包K=L101裝入總價值1麗I回溯法求解少背包問題：總價值1盹輸入物品種數(shù)背包容量輸入背包容量輸入物品的重量及其價值物品的重量及其價值調用動態(tài)規(guī)劃法求背包問題動態(tài)規(guī)劃法求解背包問題輸出所求矩陣裝入總價值回溯法求解背包問題輸出所求矩陣裝入總價值四、運行輸出結果：aim物品種數(shù)於3背總卷量C：50物品1的重量桃及基價值uElJ:物站的重量譏2及算價畫E21:WuE3J：可題：K=l101?3?essanykeytocontinuE相同的數(shù)據(jù)，求相同同的問題，用不同的方法，得到的結果，所得結果正是所求問題的最優(yōu)解，以動態(tài)規(guī)劃法驗證回溯法求解的0/背1包問題是正確的。五、調試和運行程序過程中產(chǎn)生的問題、采取的措施及獲得的相關經(jīng)驗教訓：1本.實驗中用回溯法求0/背1包問題，課本上給出的算法偽代碼只能求出背包裝入物品的最大總價值，所以我在對物品構造結構體時定義了一個型變量g用來記錄所給物品的原始順序，并在適當位置記錄裝入和不裝入背包，存儲求解路徑，從而求出原始問題的解向量X2在.本實驗中，本為增強回溯法求解0/背1包問題函數(shù)的可移植性，只定義局部變量而不定義全局變量，花費大量時間不斷改進調試都未能達到目的，走了各種彎路，最終總是因為函數(shù)之間參數(shù)無法傳遞導致運行錯誤。這讓我真正意識