回溯法實驗01背包問題

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

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

3、cw + wi <= c) /進入左子樹 cw += wi; cp += pi; Backtrack(i+1); /回溯 /回溯結束回到當前根結點 cw -= wi; cp -= pi; /進入右子樹，條件是上界值比當前最優(yōu)值大，否則就將右子樹剪掉if(Bound(i+1)>bestp) Backtrack(i+1); 測試結果 當輸入的數據有解時： 當輸入的數據無解時： 當輸入的數據稍微大點時：實驗分析在實驗中并沒有生成多組數據，進行比較，也沒有利用隨機生成函數，因為在這種有實際有關聯的問題中，利用隨機生成函數生成的數據是十分的不合適的，在此我們只需要驗證該程序是否正確即可。0-

4、1背包問題和之前的最優(yōu)裝載其實質上一樣的，都是利用解空間樹，通過深度優(yōu)先搜索子集樹，通過利用上界函數和一些剪枝策略，從而得到最優(yōu)解。由于數據較小，所以時間上并不能反映出什么東西。實驗心得在這一章的回溯算法中，我們用的比較多的就是；利用子集樹來進行問題的探索，就例如上圖是典型的一種子集樹，在最優(yōu)裝載、0-1背包都是利用了這種滿二叉樹的子集樹進行求解，然后通過深度優(yōu)先的策略，利用約束函數和上界函數，將一些不符合條件或者不包含最優(yōu)解的分支減掉，從而提高程序的效率。對于0-1背包問題我們基本上在每一個算法中都有這么一個實例，足以說明這個問題是多么經典的一個問題啊，通過幾個不同的算法求解這一問題，我也總

5、算對該問題有了一定的了解。實驗得分助教簽名附錄：完整代碼（回溯法）/0-1背包問題 回溯法求解 #include <iostream> using namespace std; template<class Typew,class Typep> class Knap /Knap類記錄解空間樹的結點信息 template<class Typew,class Typep> friend Typep Knapsack(Typep ,Typew ,Typew,int); private: Typep Bound(int i); /計算上界的函數 void Backt

6、rack(int i); /回溯求最優(yōu)解函數 Typew c; /背包容量 int n; /物品數 Typew *w; /物品重量數組¦ Typep *p; /物品價值數組 Typew cw; /當前重量 Typep cp; /當前價值 Typep bestp; /當前最后價值 ; template<class Typew,class Typep> Typep Knapsack(Typep p,Typew w,Typew c,int n); /聲明背包問題求解函數 template <class Type> inline void Swap(Type &

7、;a,Type &b); /聲明交換函數 template<class Type> void BubbleSort(Type a,int n); /聲明冒泡排序函數 int main() int n ;/物品數 int c ;/背包容量 cout<<"物品個數為："cin>>n;cout<<"背包容量為："cin>>c;int *p = new intn;/物品價值 下標從1開始 int *w = new intn;/物品重量 下標從1開始 cout<<"物品重量分

8、別為："<<endl; for(int i=1; i<=n; i+) cin>>wi; cout<<"物品價值分別為："<<endl;for(int i=1; i<=n; i+) /以二元組（重量，價值）的形式輸出每物品的信息 cin>>pi; cout<<"物品重量和價值分別為："<<endl; for(int i=1; i<=n; i+) /以二元組（重量，價值）的形式輸出每個物品的信息 cout<<"("&

9、lt;<wi<<","<<pi<<") " cout<<endl; cout<<"背包能裝下的最大價值為："<<Knapsack(p,w,c,n)<<endl; /輸出結果system("pause"); return 0; template<class Typew,class Typep> void Knap<Typew,Typep>:Backtrack(int i) if(i>n) /到達葉子

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

11、ft = 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 /定義對象類，作用相當于結構體 template<class Typew,class Typep> friend Typep Knapsack(Typep,

12、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,int n) /為Knap:Backtrack初始化 Typew W = 0; Typep P = 0; Object *Q = new Objectn;/創(chuàng)建

13、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; /創(chuàng)建Knap的對象K K.p = new Typepn+1; K.w = new Typewn+1; for(int i=1; i<=n; i+) K.pi = pQi-

14、1.ID; K.wi = wQi-1.ID; /初始化K K.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; /返回最優(yōu)解 template<class Type> void BubbleSort(Type a,int n) /記錄一次遍歷中是否有元素的交換 bool exchange; for(int i=0; i<n-1;i+) exchange = false ; for(int j=i+1;