最优装载回溯法求解........

/** * * @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] + "----"); } } } }