回溯算法解決0-1背包問題(DOC)

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告2015-2016年第2學(xué)期信息工程學(xué)院實(shí)驗(yàn)項(xiàng)目名稱：回溯算法解決0-1背包問題實(shí)驗(yàn)日期：2016年5月18一、實(shí)驗(yàn)類型:驗(yàn)證性設(shè)計(jì)性二、實(shí)驗(yàn)?zāi)康恼莆?1背包問題的回溯算法三、實(shí)驗(yàn)內(nèi)容及要求給定n種物品和一背包。物品i的重量是wi，其價(jià)值為Vi，背包的容量為Co問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大四、實(shí)驗(yàn)步驟#in clude<iostream>using n ames pace std;class Knap friend int Knap sack(i nt p ,i nt w,i nt c,i nt n );public:void p

2、rin t()for(i nt m=1;m <=n; m+) cout<<bestxm<<""cout<<e ndl;private:int Boun d(i nt i);void Backtrack(i nt i);int c;/背包容量int n; /物品數(shù)int *w;/物品重量數(shù)組int *p;/物品價(jià)值數(shù)組;int cw;/當(dāng)前重量int cp;/當(dāng)前價(jià)值int best p;/當(dāng)前最優(yōu)值int *bestx;/當(dāng)前最優(yōu)解int *x;/當(dāng)前解int Knap:Bo un d(i nt i)/計(jì)算上界int cleft=c

3、-cw;/ 剩余容量int b=c p;/以物品單位重量價(jià)值遞減序裝入物品while(i<=n&&wi<=cleft)cleft-=wi;b+=pi；i+;/裝滿背包if(i<=n)b+=pi/wi*cleft;return b;void Knap:Backtrack(i nt i)if(i> n)if(best p<cp)for(i nt j=1;j<=n;j+)bestxj=xj;best p=cp;return;if(cw+wi<=c) / 搜索左子樹 xi=1;cw+=wi;cp+=pi；Backtrack(i+1);cw-=w

4、i;cp-=p i；if(Bound(i+1)>bestp)/ 搜索右子樹xi=0;Backtrack(i+1);class Objectfriend int Knap sack(i nt p ,i nt w,i nt c,i nt n);public:int op erator<=(Object a)c onst retur n (d>=a.d);private:int ID;float d;int Knap sack(i nt p ,i nt w,i nt c,i nt n) /為 Knap:Backtrack 初始化int W=0;int P=0;int i=1;Obj

5、ect *Q=new Object n;for(i=1;i<=n ;i+)Qi-1.ID=i;Qi-1.d=1.0* pi/wi;P+=Pi；W+=wi;if(W<=c)return P;/裝入所有物品/依物品單位重量排序float f;for( i=0;i <n ;i+)for(i nt j=i;j< n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;KnapK;K.p = new in t n+1;K.w = new in t n+1;K.x = new in t n+1;K.bestx = new intn+1;K.x0=0

6、;K.bestxO=O;for( i=1;i<=n ;i+) K.p i=p Qi-1.ID;K.wi=wQi-1.ID;K.c p=O;K.cw=O;K.c=c;K. n=n;K.bestp=0;/回溯搜索K.Backtrack(1);K. prin t();delete Q;delete K.w;delete K.p;return K.best p;void main()int *p ;i nt *w; int c=0;i nt n=0;i nt i=0;cout<<"請(qǐng)輸入背包個(gè)數(shù)："<<e ndl;cin>>n;p=new

7、intn+1;w=new intn +1;p0=0;w0=0;cout<<"請(qǐng)輸入各背包的價(jià)值:"<<e ndl;for(i=1;i<=n ;i+)cin >> pi;cout<<"請(qǐng)輸入各背包的重量:"<<e ndl;for(i=1;i<=n ;i+)cin> >wi;cout<<"請(qǐng)輸入背包容量："<<e ndl;cin >>c;cout<<K nap sack (p, w,c, n)<<

8、en dl;五、實(shí)驗(yàn)結(jié)果1、實(shí)驗(yàn)圖形請(qǐng)輸入背包個(gè)數(shù)：4請(qǐng)輸入各背包的價(jià)值：30 25 26 15請(qǐng)輸入各背包的重量：4 2 3 1請(qǐng)輸入背包容量：12 3 40 0 0 115Press anv kev to continue2、結(jié)果分析輸入背包個(gè)數(shù)為4個(gè)，背包價(jià)值分別為30 25 26 15,背包重量分別為4 2 3 1,背包的容量分別為1 2 3 4,則得出的背包算法為 0 0 0 1,最優(yōu)值為15。3、實(shí)驗(yàn)總結(jié)本次的實(shí)驗(yàn)過程中，遇到了一些小問題。最終通過百度的方式解決了，同時(shí)也讓自己了解到所謂回溯法就是指為了避免生成不可能產(chǎn)生最優(yōu)解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn) 生所需解的活結(jié)點(diǎn)，以此來減少問題的計(jì)算量，這種具有限界函數(shù)的深度優(yōu)先 生成法就稱為回溯法。C+