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

《回溯法解0-1背包問題實(shí)驗(yàn)報告》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實(shí)驗(yàn)4回溯法解0-1背包問題一、實(shí)驗(yàn)要求1．要求用回溯法求解0-1背包問題；2．要求交互輸入背包容量，物品重量數(shù)組，物品價值數(shù)組；3．要求顯示結(jié)果。二、實(shí)驗(yàn)儀器和軟件平臺儀器：帶usb接口微機(jī)軟件平臺：WIN-XP+VC++6.0三、實(shí)驗(yàn)源碼#include"stdafx.h"#include#include#include#includeusingnamespacestd;templateclassKnap{public:friendvoidInit();friendvoidKnaps

2、ack();friendvoidBacktrack(inti);friendfloatBound(inti);booloperator<(Knapa)const{if(flvoidSort(Knap*li,intn){inti,j,k;Knapminl;for(i=1;i

3、li[0];k=0;for(j=1;j<=n-i;j++){if(minl*bag=NULL;intcp=0,cw=0;intbestp=0;}usingnamespacejie;voidInit(){inti=0;cout<>n;cout<>c;cout<

4、ewKnap[n];x=newint[n];cout<<"請依次輸入"<>bag[i].w;cout<>bag[i].v;for(i=0;i=n)//到達(dá)葉節(jié)點(diǎn){bestp=cp;/

5、/更新最優(yōu)價值return;}if(cw+bag[i].w<=c)//進(jìn)入左子樹{bag[i].flag=1;cw+=bag[i].w;cp+=bag[i].v;Backtrack(i+1);cw-=bag[i].w;cp-=bag[i].v;}if(Bound(i+1)>bestp)//進(jìn)入右子樹{bag[i].flag=0;Backtrack(i+1);}}//計算當(dāng)前節(jié)點(diǎn)處的上界floatBound(inti){intcleft=c-cw;//剩余容量floatb=cp;while(i

6、=bag[i].w;b+=bag[i].v;i++;}//裝滿背包if(i

7、i<=n;i++){cout<

8、**********回溯法解0-1背包問題**********

9、"<