回溯法實(shí)驗(yàn)01背包問題

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

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

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

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

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

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

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

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

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

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

11、ft = c - cw; / 剩余容量 Typep b = cp; / 以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i <= n && wi <= cleft) cleft -= wi; b += pi; i+; / 如果背包剩余容量不足以裝下一個(gè)物品 if (i <= n) b += pi/wi * cleft; /則將物品的部分裝入到背包中 return b; class Object /定義對(duì)象類，作用相當(dāng)于結(jié)構(gòu)體 template<class Typew,class Typep> friend Typep Knapsack(Typep,

12、Typew ,Typew,int); public: int operator >= (Object a)const /符號(hào)重載函數(shù)，重載>=符號(hào) return (d>=a.d); private: int ID; /編號(hào) float d; /單位重量的價(jià)值 ; 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類的對(duì)象數(shù)組¦ /初始化Object類的對(duì)象數(shù)組¦ 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; /依物品單位重量?jī)r(jià)值降序排序 BubbleSort(Q,n); Knap<Typew,Typep> K; /創(chuàng)建Knap的對(duì)象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;