资源描述：
《01背包分支限定法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、0—1背包问题一、实验目的学习掌握分支限定法思想。二、实验内容用分支限定法求解0—1背包问题，并输出问题的最优解。0—1背包问题描述如下：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。三、实验条件Jdk1.5以上四、需求分析对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。五、基本思想：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。六、详细设计/**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;//上界函数bound计算节点所相应价值的上界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将一个新的活节点插入到子集树和优先队列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//将一个新的活节点插入到子集树和最大堆中BBnodeb=newBBn
5、ode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoublebbKnapsack(){//TODO自动生成方法存根//优先队列式分支限界法，返回最大价值，bestx返回最优解//初始化BBnodeenode=null;inti=1;doublebestp=0;//当前最优值doubleup=bound(1);//当前上界while(i!=n+1){//非叶子节点//检查当前扩展节点的右儿子子节点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返回最优解c=cc;n=pp.length-1;//定义以单位重量价值排序的物品数组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);//初始化数据成员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
