1、回 溯 法 實 驗 （ 0- 1 背 包問題）算法分析與設計實驗報告第丄次附加實驗姓名學號班級時間12.26上午地點工訓樓309實驗名稱回溯法實驗(0-1背包問題)實驗目的1. 掌握回溯法求解問題的思想2. 學會利用其原理求解0-1背包問題實驗原理基本思想：0-1背包冋題是子集選取冋題。0-1背包冋題的解空間可以用子集樹 表示。在搜索解空間樹時，只要其左兒子節點是一個可行節點，搜 索就進入左子樹。當右子樹中有可能含有最優解時，才進入右子樹 搜索。否則，將右子樹剪去。基本解題步驟：(1) 針對所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結構；以深度優先方式搜索解空間，并在搜索過程中用

2、剪枝函數避免 無效搜索。實驗步驟(1) 首先搜索解空間樹，判斷是否到達了葉結點；(2) 如果左子結點是一個可行節點，就進入左子樹；(3) 當右子樹有可能包含最優解的時候才進入右子樹，計算右子 樹上界的更好的方法是將剩余物品依次按其單位價值排序，然后依 次裝入物品，直至裝不下時，再裝入物品一部分而裝滿背包；(4) 利用深度優先搜索整個解空間樹，直到將所有的最優解找出 位置。關鍵代碼template vclass Typew, class Typep> void Knap<Typew,Typep>:Backtrack( int i) if (i>n)/到達葉子節點bestp

3、 = cp;/更新最優值return ;if (cw + wi <= c)/ 進入左子樹cw += wi;cp += pi；Backtrack(i+1);/ 回溯/回溯結束回到當前根結點cw -= wi;cp -= pi；/進入右子樹，條件是上界值比當前最優值大，否則就將右子樹 剪掉if (Bound(i+1)>bestp)Backtrack(i+1);當輸入的數據有解時:測試結果當輸入的數據無解時:當輸入的數據稍微大點時:四回溯法Xfufo OReDebuqzeno cnejext閥品上數為：M實驗分析巔I軌鬻123EC70?1O牧品價值分別為：12345678? 10妝品重量和

4、忙值分別為；<22> <3,3> <4.4>OSJ C9,9) <18,10>在實驗中并沒有生成多組數據，進行比較，也沒有利用隨機生 成函數，因為在這種有實際有關聯的問題中，利用隨機生成函數生 成的數據是十分的不合適的，在此我們只需要驗證該程序是否正確 即可。0-1背包問題和之前的最優裝載其實質上一樣的，都是利用 解空間樹，通過深度優先搜索子集樹，通過利用上界函數和一些剪 枝策略，從而得到最優解。由于數據較小，所以時間上并不能反映 出什么東西。實驗心得在這一章的回溯算法中，我們用的比較多的就是；利用子集樹 來進行問題的探索，就例如上圖是典型的一種

5、子集樹，在最優裝 載、0-1背包都是利用了這種滿二叉樹的子集樹進行求解，然后通 過深度優先的策略，利用約束函數和上界函數，將一些不符合條件 或者不包含最優解的分支減掉，從而提高程序的效率。對于0-1背包問題我們基本上在每一個算法中都有這么一個實例，足以說明這 個問題是多么經典的一個問題啊，通過幾個不同的算法求解這一問 題，我也總算對該問題有了一定的了解。助教簽名實驗得分附錄：完整代碼(回溯法)0-1背包問題 回溯法求解#i nclude <iostream>using namespacestd;template <class Typew, class Typep>cla

6、ss Knap/Knap類記錄解空間樹的結點信息template <class Typew, class Typep>friend Typep Knapsack(Typep ,Typew ,Typew,int );private :Typep Bound( int i);/計算上界的函數void Backtrack( int i);/回溯求最優解函數Typew c;/背包容量int n;/物品數Typew *w;/物品重量數組|Typep *p;/物品價值數組Typew cw;/當前重量Typep cp;/當前價值Typep bestp;/當前最后價值;template <c

7、lass Typew, class Typep>Typep Knapsack(Typep p,Typew w,Typew c, int n);/聲明背包問題求解函數template < class Type>in li nevoid Swap (Type &a,Type & b);/ 聲明交換函數template <class Type>void BubbleSort(Type a, int n);/ 聲明冒泡排序函數int main()int n ; /物品數int c ; /背包容量cout«"物品個數為："cin

8、»n;cout«"背包容量為："cin> >c;int *p = new int n; /物品價值 下標從1開始int *w = new int n; /物品重量 下標從1開始cout«"物品重量分別為："<<e ndl;for (int i=1; i<=n; i+)cin> >wi;cout«"物品價值分別為："<<e ndl;for (int i=1; i<=n; i+)/以二元組(重量，價值)的形式輸出每物品的信息cin>

9、>pi;coutvv "物品重量和價值分別為："<<e ndl;for (int i=1; i<=n; i+)/以二元組(重量，價值)的形式輸出每個物品的信息coutvv "(" <<wi<< "," <<pi<< ")"coutvve ndl;coutvv "背包能裝下的最大價值為："<<Knapsack(p,w,c,n)<<endl;/輸出結果system( "pause");

10、return 0;template vclass Typew, class Typep>void Knap<Typew,Typep>:Backtrack( int i)if (i>n)/到達葉子節點bestp = cp;/更新最優值return ;if (cw + wi <= c)/ 進入左子樹cw += wi;cp += pi；Backtrack(i+1);/ 回溯/回溯結束回到當前根結點cw -= wi;cp -= pi；/進入右子樹，條件是上界值比當前最優值大，否則就將右子樹剪掉if (Bound(i+1)>bestp)Backtrack(i+1);t

11、emplate <class Typew, class Typep>Typep KnapvTypew, Typep>:Bound( int i) /計算上界Typew cleft = c - cw;/ 剩余容量Typep b = cp;/以物品單位重量價值遞減序裝入物品while (i <= n && wi <= cleft)cleft -= wi;b += pi;i+;/如果背包剩余容量不足以裝下一個物品if (i <= n)b += pi/wi * cleft;/則將物品的部分裝入到背包中return b;class Object /定義

12、對象類，作用相當于結構體template vclass Typew, class Typep>friend Typep Knapsack(Typep,Typew ,Typew, int ); public :int operator >= (Object a) const / 符號重載函數，重載 >=符號return (d>=a.d);private :int ID; / 編號float d; /單位重量的價值;template <class Typew, class Typep>Typep Knapsack(Typep p,Typew w,Typew c,

13、 int n)/ 為 Knap:Backtrack 初始化Typew W = 0;Typep P = 0;Object *Q =newObjectn; / 創建 Object 類的對象數組 |/初始化Object類的對象數組|for (int i=1; i<=n; i+)Qi-1 .ID = i;Qi-1.d = 1.0 * pi/wi;P += pi;W += wi;if (W <= c) /裝入所有物品return P;/依物品單位重量價值降序排序BubbleSort(Q, n);Knap<Typew,Typep> K;/ 創建 Knap的對象 KK.p =n ew

14、Typep n+1;K.w =n ewTypew n+1;for (int i=1; i<=n; i+)K.pi = pQi-1D;K.wi = wQi-1.ID;/初始化KK.cp = 0;K.cw = 0;K.c = c;K.n = n;K.bestp = 0;/回溯搜索K.Backtrack(1);delete Q;delete K.w;delete K.p;return K.bestp; / 返回最優解 template <class Type>void BubbleSort(Type a, int n) /記錄一次遍歷中是否有元素的交換bool excha nge;for (int i=0; i<n-1;i+)exchange = false ;for (int