資源描述：
《01背包分支限定法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、0—1背包問題一、實驗?zāi)康膶W(xué)習掌握分支限定法思想。二、實驗內(nèi)容用分支限定法求解0—1背包問題，并輸出問題的最優(yōu)解。0—1背包問題描述如下：給定n種物品和一背包。物品i的重量是Wi，其價值為Vi，背包的容量是c，問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。三、實驗條件Jdk1.5以上四、需求分析對于給定n種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價值最大化。五、基本思想：對物品的選取與否構(gòu)成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優(yōu)解，并用結(jié)點上界殺死不符合要求的結(jié)點。六、詳細設(shè)計/**Bound_Branch.java**Creat
2、edon2007年6月2日,下午6:07**Tochangethistemplate,chooseTools
3、TemplateManager*andopenthetemplateintheeditor.*/packagesunfa;publicclassBound_Branch{staticdoublec;staticintn;staticdouble[]w;staticdouble[]p;staticdoublecw;staticdoublecp;staticint[]bestX;staticMaxHeapheap;//上界函數(shù)bound計算節(jié)點所相應(yīng)價值的上界privatestati
4、cdoublebound(inti){doublecleft=c-cw;doubleb=cp;while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝填剩余容量裝滿背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}//addLiveNode將一個新的活節(jié)點插入到子集樹和優(yōu)先隊列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//將一個新的活節(jié)點插入到子集樹和最大堆中BBnodeb=newBBn
5、ode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoublebbKnapsack(){//TODO自動生成方法存根//優(yōu)先隊列式分支限界法，返回最大價值，bestx返回最優(yōu)解//初始化BBnodeenode=null;inti=1;doublebestp=0;//當前最優(yōu)值doubleup=bound(1);//當前上界while(i!=n+1){//非葉子節(jié)點//檢查當前擴展節(jié)點的右兒子子節(jié)點doublewt=cw+w[i];if(wt<=c){if(cp+p[i]>be
6、stp)bestp=cp+p[i];addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);}up=bound(i+1);if(up>=bestp)addLiveNode(up,cp,cw,i+1,enode,false);HeapNodenode=(HeapNode)heap.removeMax();enode=node.liveNode;cw=node.weight;cp=node.profit;up=node.upperProfit;i=node.level;}for(intj=n;j>0;j--){bestX[j]=(enode.leftCh
7、ild)?1:0;enode=enode.parent;}returncp;}publicstaticdoubleknapsack(double[]pp,double[]ww,doublecc,int[]xx){//返回最大值，bestx返回最優(yōu)解c=cc;n=pp.length-1;//定義以單位重量價值排序的物品數(shù)組Element[]q=newElement[n];doublews=0.0;doubleps=0.0;for(inti=1;i<=n;i++){q[i-1]=newElement(i,pp[i]/ww[i]);ps+=pp[i];ws+=ww[i];}if(ws<=c){
8、for(inti=1;i<=n;i++)xx[i]=1;returnps;}//以單位重量排序MergeSort.mergeSort(q);//初始化數(shù)據(jù)成員p=newdouble[n+1];w=newdouble[n+1];for(inti=1;i<=n;i++){p[i]=pp[q[n-i].id];w[i]=ww[q[n-i].id];}cw=0.0;cp=0.0;bestX=newint[n+1];heap=newMaxHe
