實(shí)驗(yàn)報(bào)告 回溯法01背包

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

1、《算法設(shè)計(jì)與分析》實(shí)驗(yàn)報(bào)告六學(xué)號(hào)：1004091130姓名：金玉琦日期：2011-11-17得分：一、實(shí)驗(yàn)內(nèi)容：運(yùn)用回溯法解決0-1背包問題二、所用算法的基本思想及復(fù)雜度分析：回溯法回溯法就是一種有組織的系統(tǒng)化搜索技術(shù),可以看作是蠻力法窮舉搜索的改進(jìn)?；厮莘看沃粯?gòu)造可能解的一部分,然后評(píng)估這個(gè)部分解,如果這個(gè)部分解有可能導(dǎo)致一個(gè)完整解,則對(duì)其進(jìn)一步構(gòu)造,否則,就不必繼續(xù)構(gòu)造這個(gè)部分解了。回溯法常?？梢员苊馑阉魉械目赡芙狻?-1背包問題1）基本思想給定n種物品和一個(gè)容量為C的背包,物品i的重量是Wi,其價(jià)值為Vi,0/

2、1背包問題是如何選擇裝入背包的物品(物品不可分割),使得裝入背包中物品的總價(jià)值最大，設(shè)計(jì)可能解的表示方式,構(gòu)成解空間樹。2）復(fù)雜度分析時(shí)間復(fù)雜度是O(2n);三、源程序及注釋：#includeusingnamespacestd;classKnap{friendintKnapsack(intp[],intw[],intc,intn);public:voidprint(){for(intm=1;m<=n;m++){cout<

3、und(inti);5voidBacktrack(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;//以物品單位重量價(jià)值遞減序裝入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=

4、p[i];i++;}//裝滿背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}voidKnap::Backtrack(inti){if(i>n){if(bestpbestp)//搜索右子樹{x[

5、i]=0;Backtrack(i+1);}}classObject{friendintKnapsack(intp[],intw[],intc,intn);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;floatd;};intKnapsack(intp[],intw[],intc,intn){//為Knap::Backtrack初始化intW=0;intP=0;inti=1;Object*Q=newObject[n];for(i=1;i<=

6、n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)5returnP;//裝入所有物品//依物品單位重量排序floatf;for(i=0;i

7、;K.x[0]=0;K.bestx[0]=0;for(i=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);K.print();delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}voidmain(){int*p;int*w;5intc=0;intn=0;inti=0;cout<<"請(qǐng)輸入背包個(gè)數(shù)："<

8、dl;cin>>n;p=newint[n+1];w=newint[n+1];p[0]=0;w[0]=0;cout<<"請(qǐng)輸入個(gè)背包的價(jià)值："<>p[i];cout<<"請(qǐng)輸入個(gè)背包的重量："<>w[i];cou