loading1.java

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

//P155 增加上界函数

public class Loading1 {
    //类数据成员
    static int n;                //集装箱数  
    static int[] w;              //集装箱重量数组   
    static int c;              //第一艘轮船的载重量
    static int cw;               //当前载重量
    static int bestw;            //当前最优载重量
    static int r;                //剩余集装箱重量
    
    public static int maxLoading(int []ww,int cc)
    {
    	//初始化类数据成员
    	n=ww.length-1;
    	w=ww;
    	c=cc;
    	cw=0;
    	bestw=0;
    	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){//到达叶结点 
    	   if(cw>bestw)bestw=cw;
    	   return;    	
    	}
    	//搜索子树
    	r-=w[i];
    	if(cw+w[i]<=c){//搜索左子树，即x[i]=1
    		cw+=w[i];
    		backtrack(i+1);
    		cw-=w[i];
    	}
    	if(cw+r>bestw)
    	  backtrack(i+1);//搜索右子树
    	r+=w[i];
    }




    public static void main(String[] args) {
      int[]w1={10,20,20};   //集装箱重量数组
      int c1=40;            //第一艘轮船的载重量
      maxLoading(w1,c1);  
      System.out.println(bestw);
    }
}