回溯法實(shí)驗(yàn)(0

1、回 溯 法 實(shí) 驗(yàn) （ 0- 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)；以深度優(yōu)先方式搜索解空間，并在搜索過程中用

2、剪枝函數(shù)避免 無效搜索。實(shí)驗(yàn)步驟(1) 首先搜索解空間樹，判斷是否到達(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 vclass Typew, class Typep> void Knap<Typew,Typep>:Backtrack( int i) if (i>n)/到達(dá)葉子節(jié)點(diǎn)bestp

3、 = 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);當(dāng)輸入的數(shù)據(jù)有解時(shí):測(cè)試結(jié)果當(dāng)輸入的數(shù)據(jù)無解時(shí):當(dāng)輸入的數(shù)據(jù)稍微大點(diǎn)時(shí):四回溯法Xfufo OReDebuqzeno cnejext閥品上數(shù)為：M實(shí)驗(yàn)分析巔I軌鬻123EC70?1O牧品價(jià)值分別為：12345678? 10妝品重量和

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

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

6、ss 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 Backtrack( 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 <c

7、lass Typew, class Typep>Typep Knapsack(Typep p,Typew w,Typew c, int n);/聲明背包問題求解函數(shù)template < class Type>in li nevoid Swap (Type &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

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

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

10、return 0;template vclass Typew, class Typep>void Knap<Typew,Typep>:Backtrack( int i)if (i>n)/到達(dá)葉子節(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);t

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

12、對(duì)象類，作用相當(dāng)于結(jié)構(gòu)體template vclass Typew, class Typep>friend Typep Knapsack(Typep,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,

13、 int n)/ 為 Knap:Backtrack 初始化Typew W = 0;Typep P = 0;Object *Q =newObjectn; / 創(chuàng)建 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;/依物品單位重量價(jià)值降序排序BubbleSort(Q, n);Knap<Typew,Typep> K;/ 創(chuàng)建 Knap的對(duì)象 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; / 返回最優(yōu)解 template <class Type>void BubbleSort(Type a, int n) /記錄一次遍歷中是否有元素的交換bool excha nge;for (int i=0; i<n-1;i+)exchange = false ;for (int