資源描述：
《算法 0-1背包問(wèn)題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、一、實(shí)驗(yàn)?zāi)康呐c要求掌握回溯法、分支限界法的原理，并能夠按其原理編程實(shí)現(xiàn)解決0-1背包問(wèn)題，以加深對(duì)回溯法、分支限界法的理解。1．要求分別用回溯法和分支限界法求解0-1背包問(wèn)題；2．要求交互輸入背包容量，物品重量數(shù)組，物品價(jià)值數(shù)組；3．要求顯示結(jié)果。二、實(shí)驗(yàn)方案在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。三、實(shí)驗(yàn)結(jié)果和數(shù)據(jù)處理1．用回溯法解決0-1背包問(wèn)題：代碼：importjava.util.*;publicclassKnapsack{privatedouble[]p,w;//分別代表價(jià)值和重量priv
2、ateintn;privatedoublec,bestp,cp,cw;privateintx[];//記錄可選的物品privateint[]cx;publicKnapsack(doublepp[],doubleww[],doublecc){this.p=pp;this.w=ww;this.n=pp.length-1;this.c=cc;this.cp=0;this.cw=0;this.bestp=0;x=newint[ww.length];cx=newint[pp.length];}voidKnapsack(){backtrack(0);}voidbacktrack(inti){if
3、(i>n){//判斷是否到達(dá)了葉子節(jié)點(diǎn)if(cp>bestp){for(intj=0;j4、背包容量：c=7");System.out.println("物品重量數(shù)組：w={3,5,2,1}");System.out.println("物品價(jià)值數(shù)組：p={9,10,7,4}");System.out.println("最優(yōu)值：="+bestp);System.out.println("選中的物品是:");for(inti=0;i5、weight=7;Knapsackks=newKnapsack(p,w,maxweight);ks.Knapsack();//回溯搜索ks.printResult();}}運(yùn)行結(jié)果：2．用優(yōu)先隊(duì)列式分支限界法解決0-1背包問(wèn)題：代碼：publicclassKnapsack{staticdoublec;staticintn;staticdoublew[];staticdoublep[];staticdoublecw;staticdoublecp;staticintbestX[];staticMaxHeapheap;//上界函數(shù)bound計(jì)算結(jié)點(diǎn)所相應(yīng)價(jià)值的上界privatestatic
6、doublebound(inti){doublecleft=c-cw;doubleb=cp;while(i<=n&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//裝填剩余容量裝滿背包if(i<=n)b=b+p[i]/w[i]*cleft;returnb;}//addLiveNode將一個(gè)新的活結(jié)點(diǎn)插入到子集樹(shù)和優(yōu)先隊(duì)列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//將一個(gè)新的活結(jié)點(diǎn)插入到子集樹(shù)和最大堆中BBnode
7、b=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoubleMaxKnapsack(){//優(yōu)先隊(duì)列式分支限界法，返回最大價(jià)值，bestx返回最優(yōu)解BBnodeenode=null;inti=1;doublebestp=0;//當(dāng)前最優(yōu)值doubleup=bound(1);//當(dāng)前上界while(i!=n+1){//非葉子結(jié)點(diǎn)
