回溯法實驗(0-1背包問題)

算法分析與設計實驗報告

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

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

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