backtrace.java

01背包问题

/*
 * BackTrace.java
 *
 * Created on 2007年6月15日, 下午6:09
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package sunfa;

import java.util.Date;


public class BackTrace {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		double w[]={2,2,6,5,4};
		double v[]={6,3,5,4,6};
		int n=5;
		double c=10;
		knapsack(v,w,c);
		System.out.println(bestp);
		
	}
        //比较两个元素大小的类
	private static class Element implements Comparable{ 
		int id;
		double d;
		
		private 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;
		}
	}

	static double c; //背包容量
	static int n;//物品数
	static double[]w;//物品重量数组
	static double[]p; //物品价值数组
	static double cw;//当前重量
	static double cp;//当前价值
	static double bestp; //当前最优值
	static int [] x;//解
	static int [] sortX;//排好序之后的解
	static int [] bestX;//最有解
   
	
	static Date date = null;  //  @jve:decl-index=0:
	
	public static double knapsack(double[]pp,double[]ww,double cc){
		
		c=cc;
		n=pp.length-1;
		cw=0.0;
		cp=0.0;
		bestp=0.0;
		
		Element[]q=new Element[n];
		 //q为单位重量价值数组
		for(int i=1;i<=n;i++)
			q[i-1]=new Element(i,pp[i]/ww[i]);
			
			MergeSort.mergeSort(q);
			
			p=new double[n+1];
			w=new double[n+1];
			x=new int[n+1];
			sortX=new int[n+1];
			bestX=new int[n+1];
			for(int i=1;i<=n;i++){
				p[i]=pp[q[n-i].id];
				w[i]=ww[q[n-i].id];
				sortX[i]=q[n-i].id;
			}
			
			backtrack(1);//回溯搜索
			
			
			 return bestp;
	}
	
	private static void backtrack(int i){
		if(i>=n){
			if(cp>bestp){
			   bestp=cp;
			
			for(int j=1;j<=n;j++){
				bestX[j]=x[j];
			}
			}
			return;
		}
            //搜索子树
		if(cw+w[i]<=c){
                    //进入左子树
			x[sortX[i]]=1;
			cw+=w[i];
			cp+=p[i];
			backtrack(i+1);
			cw-=w[i];
			cp-=p[i];
			
		}
		if(bound(i+1)>bestp)
			x[sortX[i]]=0;
			backtrack(i+1);//进入右子树
	}
	//计算上界
	private static double bound(int i){
		double cleft=c-cw;
		double bound=cp;
                //以物品重量价值递减顺序装入物品
		while(i<=n&&w[i]<=cleft){
			cleft-=w[i];
			bound+=p[i];i++;
			
		}
            //装满背包
		if(i<=n)
			bound+=p[i]/w[i]*cleft;
		return bound;
	}
	public static String getX(){
		String solution=String.valueOf(bestX[1]);
		for(int i=2;i<bestX.length;i++){
			solution+=",";
			solution+=String.valueOf(bestX[i]);
		}
		return solution;
	}
	public static double getBestValue(){
		
		return bestp;
	}

  
}