回溯法解背包問題實驗報告

1、實驗4回溯法解0-1背包問題一 、實驗要求1要求用回溯法求解0-1 背包問題；2要求交互輸入背包容量，物品重量數(shù)組，物品價值數(shù)組；3要求顯示結(jié)果。二 、實驗儀器和軟件平臺儀器 ：帶 usb 接口微機(jī)軟件平臺： WIN-XP + VC+6.0三 、實驗源碼#include "stdafx.h"#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;template<class ty>class Kn

2、appublic:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator<(Knap<ty> a)constif(fl<a.fl)return true;elsereturn false;private:ty w;/重量ty v;/價值float fl;/單位重量的價值v/wint kk;/記錄第幾個物品int flag;/記錄是否放入包中;template<class ty>void Sort

3、(Knap<ty> *li,int n)int i,j,k;Knap<ty> minl;for(i=1;i<n;i+)minl=li0;k=0;for(j=1;j<=n-i;j+)if(minl<lij)minl=lij;swap(lij,lik);k=j;namespace jie /命名空間int c=0,n=0;int *x=NULL;Knap<int> *bag=NULL;int cp=0,cw=0;int bestp=0;using namespace jie;void Init()int i=0;cout<<endl

4、;cout<<" 請輸入物品數(shù)量n = "cin>>n; cout<<endl;cout<<" 請輸入背包容量C = "cin>>c; cout<<endl;bag=new Knap<int> n;x=new intn;cout<<" 請依次輸入 "<<n<<" 個物品的重量W:"<<endl;for(i=0;i<n;i+)cin>>bagi.w;cout<&l

5、t;endl;cout<<" 請依次輸入 "<<n<<" 個物品的價值P:"<<endl;for(i=0;i<n;i+)cin>>bagi.v;for(i=0;i<n;i+)bagi.flag=0;bagi.kk=i;bagi.fl=1.0*bagi.v/bagi.w;void Backtrack(int i)if(i>=n) /到達(dá)葉節(jié)點(diǎn)bestp=cp; /更新最優(yōu)價值return;if(cw+bagi.w<=c) /進(jìn)入左子樹bagi.flag=1; cw+=bag

6、i.w;cp+=bagi.v; Backtrack(i+1);cw-=bagi.w; cp-=bagi.v;if(Bound(i+1)>bestp)/進(jìn)入右子樹bagi.flag=0; Backtrack(i+1);/ 計算當(dāng)前節(jié)點(diǎn)處的上界float Bound(int i)int cleft = c-cw; /剩余容量float b = cp;while (i<n&&bagi.w<=cleft)/ 以物品單位重量價值遞減序裝入cleft-=bagi.w ;b+=bagi.v;i+;/ 裝滿背包if (i<n) b+=1.0*bagi.v/bagi.w

7、* cleft;return b;void Knapsack() /計算最優(yōu)解和變量值int L(0);/用 L 累計價值，初始價值設(shè)置為0for(int k=0;k<n;k+)xbagk.kk=bagk.flag; /x=0表示未放入背包，x=1 表示放入背包L+=bagk.flag*bagk.v; /價值累加cout<<endl;cout<<" 當(dāng)前最優(yōu)價值為 :"<<L<<endl;cout<<" 變量值 x = "for(int i=1;i<=n;i+)cout<<xi-1;delete bag; bag=NULL;delete x; x=NULL;cout<<endl; getch();int main()cout<<endl;cout<<"|*回溯法解 0-1 背包問題 *|"<<endl;Init();Backtrack(0);Knapsack();return 0;四 、運(yùn)行結(jié)果五 、實驗小結(jié)通過該實驗， 我充分了解了回溯法與分支界限法的區(qū)別。