回溯算法解決0-1背包問(wèn)題

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告2015-2016年第2學(xué)期實(shí)驗(yàn)班級(jí)：學(xué)生姓名：學(xué)號(hào)：指導(dǎo)老師：信息工程學(xué)院實(shí)驗(yàn)項(xiàng)目名稱：回溯算法解決0-1背包問(wèn)題實(shí)驗(yàn)日期：2016年5月18日一、實(shí)驗(yàn)類型：以驗(yàn)證性口設(shè)計(jì)性二、實(shí)驗(yàn)?zāi)康恼莆?1背包問(wèn)題的回溯算法三、實(shí)驗(yàn)內(nèi)容及要求給定n種物品和一背包。物品i的重量是wi,其價(jià)值為vi,背包的容量為Co問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？四、實(shí)驗(yàn)步驟#include<iostream>usingnamespacestd;classKnapfriendintKnapsack(intp,intw,intc,intn);public:void

2、print()for(intm=1;m<=n;m+)cout<<bestxm<<""cout<<endl;private:intBound(inti);voidBacktrack(inti);intc;背包容量intn;物品數(shù)int*w;/物品重量數(shù)組int*p;/物品價(jià)值數(shù)組intcw;/當(dāng)前重量intcp;/當(dāng)前價(jià)值intbestp;/當(dāng)前最優(yōu)值int*bestx;/當(dāng)前最優(yōu)解int*x;/當(dāng)前解);intKnap:Bound(inti)(計(jì)算上界intcleft=c-cw;/剩余容量intb=cp;以物品單位重量?jī)r(jià)值遞減序裝入

3、物品while(i<=n&&wi<=cleft)(cleft-=wi;b+=pi;i+;)裝滿背包if(i<=n)b+=pi/wi*cleft;returnb;)voidKnap:Backtrack(inti)(if(i>n)(if(bestp<cp)for(intj=1;j<=n;j+)bestxj=xj;bestp=cp;return;)if(cw+wi<=c)/搜索左子樹xi=1;cw+=wi;cp+=pi;Backtrack(i+1);cw-=wi;cp-=pi;)if(Bound(i+1)>bestp)/搜索右子樹xi=

4、0;Backtrack(i+1);)classObjectfriendintKnapsack(intp,intw,intc,intn);public:intoperator<=(Objecta)constreturn(d>=a.d);)private:intID;floatd;);intKnapsack(intp,intw,intc,intn)為Knap:Backtrack初始化intW=0;intP=0;inti=1;Object*Q=newObjectn;for(i=1;i<=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W

5、<=c)returnP;/裝入所有物品依物品單位重量排序floatf;for(i=0;i<n;i+)for(intj=i;j<n;j+)if(Qi.d<Qj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;KnapK;K.p=newintn+1;K.w=newintn+1;K.x=newintn+1;K.bestx=newintn+1;K.x0=0;K.bestxO=O;for(i=1;i<=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;)K.cp=O;K.cw=O;K.c=c;K.n=n;K.bestp=O;/回溯搜索K.Backtrac

6、k(l);K.print();deleteQ;deleteK.w;deleteK.p;returnK.bestp;)voidmain()(int*p;int*w;intc=O;intn=O;inti=0;cout<<"請(qǐng)輸入背包個(gè)數(shù)："«endl;cin»n;p=newintn+1;w=newintn+1;p0=0;w0=0;cout<"請(qǐng)輸入各背包的價(jià)值："<<endl;for(i=1;i<=n;i+)cin»pi;cout<"請(qǐng)輸入各背包的重量："<&l

7、t;endl;for(i=1;i<=n;i+)cin»wi;cout<<”請(qǐng)輸入背包容量："«endl;cin»c;cout«Knapsack(p,w,c,n)«endl;)五、實(shí)驗(yàn)結(jié)果1、實(shí)驗(yàn)圖形Jc：Windowssyjtem32Debugl3213.exe*1請(qǐng)輸入背包個(gè)數(shù)，4請(qǐng)輸入各背包的價(jià)值：30252615請(qǐng)輸入各背包的重量二4231請(qǐng)輸入背包容量：1234*000115Pressanykeytocontinue2、結(jié)果分析輸入背包個(gè)數(shù)為4個(gè)，背包價(jià)值分別為30252615,背包重量分別為4231,背包的容量分別為1234,則得出的背包算法為0001,最優(yōu)值為15。3、實(shí)驗(yàn)總結(jié)本次的實(shí)驗(yàn)過(guò)程中，遇到了一些小問(wèn)題。最終通過(guò)百度的方式解決了，同時(shí)也讓自己了解到所謂回溯法就是指為了避免生成不可能產(chǎn)生最優(yōu)解的問(wèn)題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以此來(lái)減少問(wèn)題的計(jì)算量，這種具有限界函數(shù)的深度優(yōu)先生成法就稱為回溯法。總之通過(guò)本次的算法