回溯法實(shí)驗(yàn)(0-1背包問(wèn)題)

算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告

第五次附加實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間上午地點(diǎn)工訓(xùn)樓實(shí)驗(yàn)名稱(chēng)回溯法實(shí)驗(yàn)（0-1背包問(wèn)題）實(shí)驗(yàn)?zāi)康恼莆栈厮莘ㄇ蠼鈫?wèn)題的思想學(xué)會(huì)利用其原理求解背包問(wèn)題實(shí)驗(yàn)原理基本思想：0-1背包問(wèn)題是子集選取問(wèn)題。0-1背包問(wèn)題的解空間可以用子集樹(shù)表示。在搜索解空間樹(shù)時(shí)，只要其左兒子節(jié)點(diǎn)是一個(gè)可行節(jié)點(diǎn)，搜索就進(jìn)入左子樹(shù)。當(dāng)右子樹(shù)中有可能含有最優(yōu)解時(shí)，才進(jìn)入右子樹(shù)搜索。否則，將右子樹(shù)剪去?；窘忸}步驟：（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；⑶以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。實(shí)驗(yàn)步驟（1）首先搜索解空間樹(shù)，判斷是否到達(dá)了葉結(jié)點(diǎn)；（2）如果左子結(jié)點(diǎn)是一個(gè)可行節(jié)點(diǎn)，就進(jìn)入左子樹(shù)；（3）當(dāng)右子樹(shù)有可能包含最優(yōu)解的時(shí)候才進(jìn)入右子樹(shù)，計(jì)算右子樹(shù)上界的更好的方法是將剩余物品依次按其單位價(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入物品一部分而裝滿背包；（4）利用深度優(yōu)先搜索整個(gè)解空間樹(shù)，直到將所有的最優(yōu)解找出位置。關(guān)鍵代碼templatevclassTypew,classTypep>voidKnap<Typew,Typep>::Backtrack(inti){if(i>n)〃到達(dá)葉子節(jié)點(diǎn){bestp=cp;〃更新最優(yōu)值return;}if(cw+w[i]<=c)〃進(jìn)入左子樹(shù){cw+=w[i];

cp+=p[i];Backtrack(i+1);〃回溯〃回溯結(jié)束回到當(dāng)前根結(jié)點(diǎn)cw-=w[i];cp—=p[i]；}〃進(jìn)入右子樹(shù)，條件是上界值比當(dāng)前最優(yōu)值大，否則就將右子樹(shù)剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}測(cè)試結(jié)果當(dāng)輸入的數(shù)據(jù)有解時(shí):當(dāng)輸入的數(shù)據(jù)無(wú)解時(shí):當(dāng)輸入的數(shù)據(jù)稍微大點(diǎn)時(shí):

測(cè)試結(jié)果當(dāng)輸入的數(shù)據(jù)有解時(shí):當(dāng)輸入的數(shù)據(jù)無(wú)解時(shí):當(dāng)輸入的數(shù)據(jù)稍微大點(diǎn)時(shí):實(shí)驗(yàn)分析在實(shí)驗(yàn)中并沒(méi)有生成多組數(shù)據(jù)，進(jìn)行比較，也沒(méi)有利用隨機(jī)生成函數(shù)，因?yàn)樵谶@種有實(shí)際有關(guān)聯(lián)的問(wèn)題中，利用隨機(jī)生成函數(shù)生成的數(shù)據(jù)是十分的不合適的，在此我們只需要驗(yàn)證該程序是否正確即可。背包問(wèn)題和之前的最優(yōu)裝載其實(shí)質(zhì)上一樣的，都是利用解空間樹(shù)，通過(guò)深度優(yōu)先搜索子集樹(shù)，通過(guò)利用上界函數(shù)和一些剪枝策略，從而得到最優(yōu)解。由于數(shù)據(jù)較小，所以時(shí)間上并不能反映出什么東西。實(shí)驗(yàn)分析在實(shí)驗(yàn)中并沒(méi)有生成多組數(shù)據(jù)，進(jìn)行比較，也沒(méi)有利用隨機(jī)生成函數(shù)，因?yàn)樵谶@種有實(shí)際有關(guān)聯(lián)的問(wèn)題中，利用隨機(jī)生成函數(shù)生成的數(shù)據(jù)是十分的不合適的，在此我們只需要驗(yàn)證該程序是否正確即可。背包問(wèn)題和之前的最優(yōu)裝載其實(shí)質(zhì)上一樣的，都是利用解空間樹(shù)，通過(guò)深度優(yōu)先搜索子集樹(shù)，通過(guò)利用上界函數(shù)和一些剪枝策略，從而得到最優(yōu)解。由于數(shù)據(jù)較小，所以時(shí)間上并不能反映出什么東西。實(shí)驗(yàn)心得在這一章的回溯算法中，我們用的比較多的就是；利用子集樹(shù)來(lái)進(jìn)行問(wèn)題的探索，就例如上圖是典型的一種子集樹(shù)，在最優(yōu)裝載、背包都是利用了這種滿二叉樹(shù)的子集樹(shù)進(jìn)行求解，然后通過(guò)深度優(yōu)先的策略，利用約束函數(shù)和上界函數(shù)，將一些不符合條件或者不包含最優(yōu)解的分支減掉，從而提高程序的效率。對(duì)于背包問(wèn)題我們基本上在每一個(gè)算法中都有這么一個(gè)實(shí)例，足以說(shuō)明這個(gè)問(wèn)題是多么經(jīng)典的一個(gè)問(wèn)題啊，通過(guò)幾個(gè)不同的算法求解這一問(wèn)題，我也總算對(duì)該問(wèn)題有了一定的了解。實(shí)驗(yàn)得分助教簽名附錄：完整代碼(回溯法)//0-1背包問(wèn)題回溯法求解#include<iostream>usingnamespacestd;template<classTypew,classTypep>classKnap//Knap類(lèi)記錄解空間樹(shù)的結(jié)點(diǎn)信息{template<classTypew,classTypep>friendTypepKnapsack(Typep[],Typew[],Typew,int);private:TypepBound(inti);//計(jì)算上界的函數(shù)voidBacktrack(inti);//回溯求最優(yōu)解函數(shù)Typewc;//背包容量intn;//物品數(shù)Typew*w;〃物品重量數(shù)組；Typep*p;//物品價(jià)值數(shù)組Typewcw;//當(dāng)前重量Typepcp;//當(dāng)前價(jià)值Typepbestp;//當(dāng)前最后價(jià)值};template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn);//聲明背包問(wèn)題求解函數(shù)template<classType>inlinevoidSwap(Type&a,Type&b);//聲明交換函數(shù)template<classType>voidBubbleSort(Typea[],intn);//聲明冒泡排序函數(shù)intmain(){intn;//物品數(shù)intc;//背包容量cout<<"物品個(gè)數(shù)為："；cin>>n;cout<<"背包容量為：”；cin>>c;int*p=newint[n];〃物品價(jià)值下標(biāo)從1開(kāi)始int*w=newint[n];〃物品重量下標(biāo)從1開(kāi)始cout<<"物品重量分別為："<<endl;for(inti=1;i<=n;i++){cin>>w[i];}cout<<"物品價(jià)值分別為："<<endl;for(inti=1;i<=n;i++)//以二元組(重量，價(jià)值)的形式輸出每物品的信息{cin>>p[i];}cout<<"物品重量和價(jià)值分別為："<<endl;for(inti=1;i<=n;i++)//以二元組(重量，價(jià)值)的形式輸出每個(gè)物品的信息{cout<<"("<<w[i]<<","<<p[i]<<")";}cout<<endl;cout<<"背包能裝下的最大價(jià)值為："<<Knapsack(p,w,c,n)<<endl;〃輸出結(jié)果system("pause");return0;}template<classTypew,classTypep>voidKnap<Typew,Typep>::Backtrack(inti){if(i>n)//到達(dá)葉子節(jié)點(diǎn){bestp=cp;//更新最優(yōu)值return;}if(cw+w[i]<=c)//進(jìn)入左子樹(shù){cw+=w[i];cp+=p[i];Backtrack(i+1);//回溯//回溯結(jié)束回到當(dāng)前根結(jié)點(diǎn)cw-=w[i];cp-=p[i];}//進(jìn)入右子樹(shù)，條件是上界值比當(dāng)前最優(yōu)值大，否則就將右子樹(shù)剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti)//計(jì)算上界{Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品單位重量?jī)r(jià)值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//如果背包剩余容量不足以裝下一個(gè)物品if(i<=n){b+=p[i]/w[i]*cleft;//則將物品的部分裝入到背包中}returnb;}classObject//定義對(duì)象類(lèi)，作用相當(dāng)于結(jié)構(gòu)體{template<classTypew,classTypep>friendTypepKnapsack(Typep[],Typew[],Typew,int);public:intoperator>=(Objecta)const//符號(hào)重載函數(shù)，重載>=符號(hào){return(d>=a.d);}private:intID;//編號(hào)floatd;//單位重量的價(jià)值};template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn){〃為Knap::Backtrack初始化TypewW=0;TypepP=0;Object*Q=newObject[n];〃創(chuàng)建Object類(lèi)的對(duì)象數(shù)組；〃初始化Object類(lèi)的對(duì)象數(shù)組；for(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)〃裝入所有物品{returnP;}//依物品單位重量?jī)r(jià)值降序排序BubbleSort(Q,n);Knap<Typew,Typep>K;〃創(chuàng)建Knap的對(duì)象KK.p=newTypep[n+1];

K.w=newTypew[n+1];for(inti=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-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;returnK.bestp;//返回最優(yōu)解}template<classType>voidBubbleSort(Typea[],intn){//記錄一次遍歷中是否有元素的交換boolexchange;for(inti=0;i<n-1;i++){exchange=false;for(intj=i+1;j<=n-1;j++){/r/