loading3.java

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

//P158-159
public class Loading3 {

    
    public static int maxLoading(int []w,int c,int [] bestx)
    {
    	//迭代回溯
    	//返回最优载重量及其相应解
    	//初始化类数据成员
    	int i=1;//当前层
    	int n=w.length-1;
    	int [] x=new int[n+1];   //x[1:n-1]为当前路径
    	int bestw=0;          //当前最优载重量
        int cw=0;             //当前载重量       
    	int r=0;             //剩余集装箱重量
    	//初始化r
    	for(int j=1;j<=n;j++)
    		r+=w[j];
    		
    	//搜索子树
        while(true){
        	while(i<=n&&cw+w[i]<=c)
        	{
        		r-=w[i];
        		cw+=w[i];
        		x[i]=1;
        		i++;
        	}
        	if(i>n)
        	{//到达叶结点
        		for(int j=1;j<=n;j++)
        			bestx[j]=x[j];
        		bestw=cw;
        	}
        	else
        	{//进入右子树
        		r-=w[i];
        		x[i]=0;
        		i++;
        	}
        	while(cw+r<=bestw)
        	{//剪枝回溯
        	    i--;
        	    while(i>0&&x[i]==0)
        	    {//从右子树返回
        	    	r+=w[i];
        	    	i--;
        	    }
        	    if(i==0)return bestw;
        	    //进入右子树
        	    x[i]=0;
        	    cw-=w[i];
        	    i++;
        		
        	}
        }

    }
       

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