思路

目标是尽可能装上最重的货物

解空间：集装箱重量数组的子集树

设定变量

• 剩余集装箱重量
• 轮船最大载重量
• 当前最好的载重量
• 当前的载重量
• 当前层数
• 记录当前方案
• 最优方案

将剩余集装箱的重量初始化为所有集装箱的重量 (当前没有装载任何货物)

从树的第一层开始遍历，采用 根-左-右 的遍历方式

• 对于一个将要处理的节点，如果当前层数大于集装箱总数，也就是到达树的叶子节点，判断当前的载重量是否大于最优载重量

  • 若大于，则更新最优载重量，并记录当前的解方案

• 无论是不是最优解，结束递归

• 对于一个将要处理的节点，现将剩余集装箱的重量减去当前集装箱的重量 (无论装不装当前集装箱，对于剩余的集装箱而言不会再包含当前集装箱)

• 若当前的载重量加上当前集装箱的重量没有超过轮船最大载重量，则将当前集装箱的重量加入当前载重量

  • 记录当前节点为进入左子树
  • 递归调用至下一层 (已经带着取当前集装箱的重量进入下一层，递归结束表示左子树已经遍历完成)
  • 回溯，即处理不取当前集装箱，当前载重量减去当前集装箱的重量

• 若当前的载重量加上剩余的集装箱重量小于最优的载重量，意味着这条分支已经没有意义 (剪枝，避免没有必要的遍历)。

• 若存在更优的可能，递归调用层数加一，表示遍历右子树，并记录当前节点为进入右子树

• 剩余载重量加上当前集装箱重量 (表示当前层左右子树遍历完成，回溯至上一层)

代码

static int n; // 集装箱数
static int[] w; // 集装箱重量数组
static int c; // 第一艘船的载重量
static int cw; // 当前载重量
static int bestW; // 当前最优载重量
static int r; // 剩余集装箱的载重量
static int[] x; // 当前的解
static int[] bestX; // 当前最优解
// 5-1
public static int maxLoading(int[] ww, int cc, int[] xx) {
    n = ww.length - 1;
    w = ww;
    c = cc;
    bestW = 0;
    x = new int[n + 1];
    bestX = xx;
    for (int i = 1; i <= n; i++) {
        r += w[i];
    }

    backtrack1(1);
    cw = 0;
    for (int i = 1; i <= n; i++) {
        r += w[i];
    }
//        backtrack2(1);
    return bestW;
}

public static void backtrack1(int i) {
    // 到达底部
    if (i > n) {
        if (cw > bestW) {
            for (int j = 1; j <= n; ++j) {
                bestX[j] = x[j];
            }
            bestW = cw;
        }
        return;
    }

    // 是否装入当前集装箱
    r -= w[i];
    if (cw + w[i] <= c) {
        cw += w[i];
        backtrack1(i + 1);
        cw -= w[i];
    }
    // 进入右子树
    if (cw + r > bestW) {
        backtrack1(i + 1);
    }
    r += w[i];
}

public static void backtrack2(int i) {
    // 到达底部
    if (i > n) {
        if (cw == bestW) {
            for (int j = 1; j <= n; ++j) {
                bestX[j] = x[j];
            }
        }
        return;
    }

    // 是否装入当前集装箱
    r -= w[i];
    if (cw + w[i] <= c) {
        x[i] = 1;
        cw += w[i];
        backtrack2(i + 1);
        cw -= w[i];
    }
    if (cw + r > bestW) {
        x[i] = 0;
        backtrack2(i + 1);
    }
    r += w[i];
}