bound_branch.java

01背包四种算法实现(java版)

/*
 * Bound_Branch.java
 *
 * Created on 2007年6月15日, 下午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<=n&&w[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;j>0;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返回最优解
                c=cc;
		n=pp.length-1;
                //定义以单位重量价值排序的物品数组
		Element[]q=new Element[n];
		double ws=0.0;
		double ps=0.0;
		for(int i=1;i<=n;i++){
			q[i-1]=new Element(i,pp[i]/ww[i]);
			ps+=pp[i];
			ws+=ww[i];
		}
		if(ws<=c){
			for(int i=1;i<=n;i++)
				xx[i]=1;
			return ps;
		}
                //以单位重量排序
		MergeSort.mergeSort(q);
                //初始化数据成员
		p=new double[n+1];
		w=new double[n+1];
		for(int i=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 = new int[n+1];
		heap = new MaxHeap(n);
		double maxp = bbKnapsack();
		for(int i=1;i<=n;i++)
			xx[q[n-i].id]=bestX[i];
		return maxp;
		
	}
	public static void main(String [] args){
		double w[]={2,2,6,5,4};
		double v[]={6,3,4,5,6};
		double c=10;
		int []x = new int[5];
		double m = knapsack(v,w,c,x);
		
		for(int i=0;i<5;i++)
			System.out.print(x[i]);
	}
	
}
//子空间中节点类型
 class BBnode{
	BBnode parent;//父节点
	boolean leftChild;//左儿子节点标志

	BBnode(BBnode par,boolean ch){
		parent=par;
		leftChild=ch;
	}
}

 class HeapNode implements Comparable{
	BBnode liveNode; // 活节点
	double upperProfit; //节点的价值上界
	double profit; //节点所相应的价值
	double weight; //节点所相应的重量
	int level; // 活节点在子集树中所处的层次号
	
	//构造方法
	public HeapNode(BBnode node, double up, double pp , double ww,int lev){
		liveNode = node;
		upperProfit = up;
		profit = pp;
		weight = ww;
		level = lev;
	}
	public int compareTo(Object o) {
	
		double xup = ((HeapNode)o).upperProfit;
		if(upperProfit < xup)
			return -1;
		if(upperProfit == xup)
			return 0;
		else
			return 1;
	}
}

 class Element implements Comparable{
	int id;
	double d;
	public Element(int idd,double dd){
		id=idd;
		d=dd;
	}
	public int compareTo(Object x){
		double xd=((Element)x).d;
		if(d<xd)return -1;
		if(d==xd)return 0;
		return 1;
	}
	public boolean equals(Object x){
		return d==((Element)x).d;
	}
}
 class MaxHeap{
	 static HeapNode [] nodes;
	 static int nextPlace;
	 static int maxNumber;
	 public MaxHeap(int n){
		 maxNumber = (int)Math.pow((double)2,(double)n);
		 nextPlace = 1;//下一个存放位置
		 nodes = new HeapNode[maxNumber];
	 }
	 public static void put(HeapNode node){
		 nodes[nextPlace] = node;
		 nextPlace++;
		 heapSort(nodes);
		
	 }
	 public static HeapNode removeMax(){
		 HeapNode tempNode = nodes[1];
		 nextPlace--;
		 nodes[1] = nodes[nextPlace];
		 heapSort(nodes);
		 return tempNode;
	 }
	 private static void heapAdjust(HeapNode [] nodes,int s,int m){
		 HeapNode rc = nodes[s];
		 for(int j=2*s;j<=m;j*=2){
			
			 if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)
				 ++j;
			
			 if(!(rc.upperProfit<nodes[j].upperProfit))
				 break;
			 nodes[s] = nodes[j];
			 s = j;
		 }
		 nodes[s] = rc;
	 }
	 private static void heapSort(HeapNode [] nodes){
		 for(int i=(nextPlace-1)/2;i>0;--i){
		
			 heapAdjust(nodes,i,nextPlace-1);
		 }
	 }
		 
 }