算法设计与分析 5.2 装载问题

/********************************************************************
      5.2 装载问题

 问题描述：
 有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的轮船，其中
 集装箱 i 的重量为 w[i], 且重量之和小于 (c1 + c2)。装载问题要求确定
 是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，
 找出一种装载方案。

 容易证明，如果一个给定的装载问题有解，则采用如下的策略可以得到最优
 装载方案。
 1.首先将第一艘轮船尽可能装满。
 2.将剩余的集装箱装上第二艘轮船。

 将第一艘轮船尽可能的装满等价于选取全体集装箱的子集，使该子集中集装箱
 的重量之和最接近 c1 。因此，等价于一个特殊的　0-1　背包问题。

 因此是一棵子集树。

********************************************************************/
import java.util.*;

public class Loading {

 public static int nn;
 public static int cc;
 public static int bestww;
 public static int[] ww;
 public static int[] xx;
 public static int[] bestxx;

 
 public static int maxLoadingRE(int[] w, int c, int[] bestx) {
  nn = w.length;
  cc = c;
  bestww = 0;
  ww = w;
  bestxx = bestx;
  xx = new int[nn];
  int r = 0;
  for (int i = 0; i < nn; i++) {
      r += ww[i];
  }
  trackback(0, 0, r);
  return bestww;
 }
 
 private static void trackback(int i, int cw, int r) {
  if (i == nn) {//到达叶结点
   for (int j = 0; j < nn; j++) {
       bestxx[j] = xx[j];
   }
   bestww = cw;
   return;
  }
  if (cw + ww[i] <= cc) {
   xx[i] = 0;
   trackback(i + 1, cw + ww[i], r);
  }
  if (r - ww[i] > bestww) {
   xx[i] = 1;
   trackback(i + 1, cw, r - ww[i]);
  }
 }

    public static int maxLoading(int[] w, int c, int[] bestx) {
  int i = 0;      //当前层
  int n = w.length;    //层总数
  int[] x = new int[n];   //x[0, i]为当前选择路径
  Arrays.fill(x, -1);    //初始化为-1，0表示选择，1表示不选
  
  int bestw = 0;     //当前最优装载重量
  int[] cw = new int[n];   //当前载重量
  int[] r = new int[n];   //剩余集装箱容量
  int tor = 0;

  for (int item : w) {
      tor += item;
  }
  r[0] = tor;
  cw[0] = 0;
  //搜索子树
  while (i > -1) {
      do {
          x[i] += 1;
    if (x[i] == 0) {  //选择
        if (cw[i] + w[i] <= c) {
         if (i < n - 1) {
          cw[i + 1] = cw[i] + w[i];
          r[i + 1] = r[i];
         }
            break;
        }
    } else {    //不选
     if (r[i] - w[i] > bestw) {
      if (i < n - 1) {
       r[i + 1] = r[i] - w[i];
       cw[i + 1] = cw[i];
      }
         break;
     }
    }

      } while (x[i] < 2);

   if (x[i] < 2) {
       if (i == n - 1) {

     for (int j = 0; j < n; j++) {
         bestx[j] = x[j];
     }
     if (x[i] == 0) {
      bestw = cw[i] + w[i];   
     } else {
         bestw = cw[i];
     }
     
       } else {
           i++;
     x[i] = -1;
       }
   } else {
       i--;
   }
  }
  return bestw;
 }

 public static void main(String[] args) {
  int[] w = {20, 10, 40};
  int n = w.length;
  int c = 50;
  int[] bestx = new int[n];

  int bestw = maxLoadingRE(w, c, bestx);
  System.out.println("bestw : " + bestw);
  System.out.println(Arrays.toString(bestx));
 }
}