loading.java

最优装载回溯法求解:主要的思想就是首先将第一艘船近可能的装满

/**
 * 
 * @author wangwei
 * @version 1.0
 *@since 2007-11-25
 */
public class Loading {
	static int n = 5;
	static int[] w = {8,6,2,3};
	static int c = 10;
	static int cw;
	static int bestw;
	static int r ;
	static int[] x = new int[w.length];
	static int[] bestx;

	/**
	 * @see 利用回溯算法实现的装载算法.<br>
	 * 主要的思想就是首先将第一艘船近可能的装满，<br>
	 * 将剩下的装观察到第二艘轮船上<br>
	 * MAX[sum(WiXi)];sum(WiXi) <= c;Xi<-{0,1}, 1 <= i <= n
	 * @param int n 集装箱的数量
	 * @param int[] w 集装箱重量
	 * @param int c 第一艘轮船的载重量
	 * @param int cw 当前的载重量
	 * @param int bestw 当前的最优载重量
	 * @param int r 剩余集装箱的重量
	 * @param int[] x 当前解
	 * @param 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;
		
		//initiate the variable of w
		for(int i = 1;i<=n;i++){
			r+=w[i];
		}
		backtrack(1);
		return bestw;
	}
	
	//回溯算法的回溯部分
	public static void backtrack(int t){
		if(t>n){
			if(cw>bestw){
				for(int j = 1;j<=n;j++){
					bestx[j] = x[j];
					
				}
				bestw = cw;
				
			}
			return;
		}
		r -= w[t];
		if(cw + w[t] <=c){
			x[t] = 1;
			cw += w[t];
			backtrack(t+1);
			cw -= w[t];
		}
		if((cw+r)>bestw){
			x[t] = 0;
			backtrack(t+1);
		}
		r+= w[t];
	}
	

	public static void main(String[] args){
		System.out.println("**利用回溯算法实现的装载算法的解**");
		maxLoading(w,c,x);
		System.out.println("将以下重量的集装箱装入第一艘船：");
		/*
		for(int element:w){
			if(x[i] == 1){
				System.out.print(w[i] + " ");
			}
			i++;
		}
		*/
		for( int i = 1;i <= n;i++){
			if(x[i] == 1){
				System.out.print(w[i] + "----");
			}
		}
	}
	
}