loading2.java

,《算法设计与分析》王晓东编著

public class Loading2 {

    //类数据成员
    static int n;                //集装箱数  
    static int[] w;              //集装箱重量数组   
    static int c;              //第一艘轮船的载重量
    static int cw;               //当前载重量
    static int bestw;            //当前最优载重量
    static int r;                //剩余集装箱重量
    static int [] x;             //当前解
    static int [] bestx;         //当前最优解
    
    public static int maxLoading(int []ww,int cc,int [] xx)
    {
    	//初始化类数据成员
    	n=ww.length-1;
    	w=ww;
    	c=cc;
    	cw=0;
    	bestw=0;
    	x=new int[n+1];
    	bestx=xx;
    	r=0;
    	//初始化r
    	for(int i=1;i<=n;i++)
    		r+=w[i];
    	//计算最优载重量
    	backtrack(1);
    	return bestw;
    }
    
    //回溯算法
    private static void backtrack(int i)
    {//搜索第i层结点
    	if(i>n){//到达叶结点 
    	   for(int j=1;j<=n;j++)
    	   	bestx[j]=x[j];
    	   bestw=cw;
    	   return;    	
    	}
    	//搜索子树
    	r-=w[i];
    	if(cw+w[i]<=c){//搜索左子树，即x[i]=1
    		x[i]=1;
    		cw+=w[i];
    		backtrack(i+1);
    		cw-=w[i];
    	}
    	if(cw+r>bestw){
    	    x[i]=0;
    	    backtrack(i+1);//搜索右子树
    	}
    	r+=w[i];
    }


    public static void main(String[] args) {
      int[]w1={10,20,20};   //集装箱重量数组
      int c1=40;            //第一艘轮船的载重量
      int [] x1={0,0,0};
      maxLoading(w1,c1,x1);  
      System.out.println("最优载重量为："+bestw);
      for (int i=0;i<w1.length;i++)
        System.out.print(bestx[i]+"  ");
    }
}