回溯法-0-1背包問題.doc

《回溯法-0-1背包問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1、問題描述一、0-1背包問題給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，如何選擇才能使得物品的總價(jià)格最高？2、算法設(shè)計(jì)思想回溯法3、算法過程描述1.解空間的定義物品有裝入和不裝入兩種狀態(tài)，設(shè)裝入為1，不裝入為0，例如n=3時(shí)，解空間為{（0,0,0），（0,0,1）……（1,1,1）}2.解空間結(jié)構(gòu)的組織使用一棵子集樹來表示解空間每一條邊的權(quán)值代表裝或不裝（1或0）采用深度優(yōu)先搜索遍歷整個(gè)樹3.約束條件1）重量不超過背包的容量2）已裝入物品的價(jià)值Cp+剩余空間裝入物品的最大價(jià)值r<=最優(yōu)解bes

2、tP注*：最大價(jià)值r的求法：假設(shè)物品能夠分割，運(yùn)用貪心算法的思想，求出背包理論最大價(jià)值r4、算法實(shí)現(xiàn)及運(yùn)行結(jié)果#includeintn,c,bestp;//物品的個(gè)數(shù)，背包的容量，最大價(jià)值intp[10000],w[10000],x[10000],bestx[10000];//物品的價(jià)值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況voidBacktrack(inti,intcp,intcw){//cw當(dāng)前包內(nèi)物品重量，cp當(dāng)前包內(nèi)物品價(jià)值intj;if(i>n)//回溯結(jié)束{if(cp

3、>bestp){bestp=cp;for(i=0;i<=n;i++)bestx[i]=x[i];}}elsefor(j=0;j<=1;j++){x[i]=j;if(cw+x[i]*w[i]<=c){cw+=w[i]*x[i];cp+=p[i]*x[i];Backtrack(i+1,cp,cw);cw-=w[i]*x[i];cp-=p[i]*x[i];}}}intmain(){inti;bestp=0;printf("請(qǐng)輸入背包最大容量:");scanf("%d",&c);printf("請(qǐng)輸入物品個(gè)數(shù):")

4、;scanf("%d",&n);printf("請(qǐng)依次輸入物品的重量:");for(i=1;i<=n;i++)scanf("%d",&w[i]);printf("請(qǐng)依次輸入物品的價(jià)值:");for(i=1;i<=n;i++)scanf("%d",&p[i]);Backtrack(1,0,0);printf("最大價(jià)值為:");printf("%d",bestp);printf("被選中的物品依次是(0表示未選中，1表示選中)");for(i=1;i<=n;i++)printf("%d",best

5、x[i]);printf("");return0;}1、算法復(fù)雜度分析及算法改進(jìn)時(shí)間復(fù)雜度為O(2^n)*O(n)(求上界)=O(n2^n)