回溯法解0-1背包問題實(shí)驗(yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)4 回溯法解0-1背包問題一 、實(shí)驗(yàn)要求1 要求用回溯法求解0-1背包問題；2 要求交互輸入背包容量，物品重量數(shù)組，物品價(jià)值數(shù)組；3 要求顯示結(jié)果。二 、實(shí)驗(yàn)儀器和軟件平臺儀器 ：帶usb接口微機(jī)軟件平臺：WIN-XP + VC+6.0三 、實(shí)驗(yàn)源碼#include "stdafx.h"#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;template<class t

2、y>class Knap public: 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;else return false; private: ty w; /重量 ty v; /價(jià)值 float fl; /單位重量的價(jià)值v/w int kk; /記錄第幾個(gè)物品 int flag; /記錄是否放入包中;t

3、emplate<class ty>void Sort(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

4、jie;void Init() int i=0;cout<<endl;cout<<"請輸入物品數(shù)量 n = "cin>>n; cout<<endl;cout<<"請輸入背包容量 C = "cin>>c; cout<<endl;bag=new Knap<int> n; x=new intn;cout<<"請依次輸入"<<n<<"個(gè)物品的重量W:"<<endl;for(i=0;

5、i<n;i+)cin>>bagi.w; cout<<endl;cout<<"請依次輸入"<<n<<"個(gè)物品的價(jià)值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)價(jià)值 return;if(cw+b

6、agi.w<=c) /進(jìn)入左子樹 bagi.flag=1; cw+=bagi.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);/計(jì)算當(dāng)前節(jié)點(diǎn)處的上界float Bound(int i) int cleft = c-cw; /剩余容量 float b = cp; while (i<n&&bagi.w<=cleft) /以物品單位重量價(jià)值遞減序裝入 cleft-=bagi.w ; b+=bag

7、i.v; i+; /裝滿背包 if (i<n) b+=1.0*bagi.v/bagi.w * cleft; return b;void Knapsack() /計(jì)算最優(yōu)解和變量值int L(0); /用L累計(jì)價(jià)值，初始價(jià)值設(shè)置為0for(int k=0;k<n;k+)xbagk.kk=bagk.flag; /x=0表示未放入背包，x=1表示放入背包L+=bagk.flag*bagk.v; /價(jià)值累加cout<<endl;cout<<"當(dāng)前最優(yōu)價(jià)值為:"<<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é)果五 、實(shí)驗(yàn)小結(jié)通過該實(shí)驗(yàn)，我充分了解了回溯法與分支界限法的區(qū)別?；厮莘ㄔ?/p>