01背包分支限定法.doc

0—1背包问题 一、实验目的 学习掌握分支限定法思想。 二、实验内容 用分支限定法求解0—1背包问题，并输出问题的最优解。0—1背包问题描述如下： 给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 三、实验条件 Jdk1.5以上 四、需求分析 对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。 五、基本思想： 对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。 六、详细设计 /* * Bound_Branch.java * * Created on 2007年6月2日, 下午6:07 * * To change this template, choose Tools | Template Manager * and open the template in the editor. */ package sunfa; public class Bound_Branch { static double c; static int n; static double[]w; static double[]p; static double cw; static double cp; static int []bestX; static MaxHeap heap; //上界函数bound计算节点所相应价值的上界 private static double bound(int i){ double cleft=c-cw; double b=cp; while(i=nw[i]=cleft){ cleft-=w[i]; b+=p[i]; i++; } //装填剩余容量装满背包 if(i=n) b+=p[i]/w[i]*cleft; return b; } //addLiveNode将一个新的活节点插入到子集树和优先队列中 private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch){ //将一个新的活节点插入到子集树和最大堆中 BBnode b=new BBnode(par,ch); HeapNode node =new HeapNode(b,up,pp,ww,lev); heap.put(node); } private static double bbKnapsack(){ // TODO 自动生成方法存根 //优先队列式分支限界法，返回最大价值，bestx返回最优解 //初始化 BBnode enode=null; int i=1; double bestp=0;//当前最优值 double up=bound(1);//当前上界 while(i!=n+1){ //非叶子节点 //检查当前扩展节点的右儿子子节点 double wt=cw+w[i]; if(wt=c){ if(cp+p[i]bestp) 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); HeapNode node =(HeapNode)heap.removeMax(); enode=node.liveNode; cw=node.weight; cp=node.profit; up=node.upperProfit; i=node.level; } for(int j=n;j0;j--){ bestX[j]=(enode.leftChild)?1:0; enode=enode.parent; } return cp; } public static double knapsack(double []pp,double []ww,double cc,int []xx){ //返回最大值，bestx返回最优解