loading.java

来自「,《算法设计与分析》王晓东编著」· Java 代码 · 共 50 行

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


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