回溯法解决装载问题（Java实现）

已知有 n 个集装箱（重量分别为 w1,w2,…,wn）和 1 艘轮船，轮船的载重量为 c，要求在不超过轮船载重量的前提下，将尽可能多的集装箱装入轮船。其中，第 i 个集装箱的重量为 wi。

问题分析

为了方便描述，用解向量 X=(x1,x2,…,xn) 表示哪一个集装箱装入轮船，其中，xi∈{0, 1}，1≤i≤n，xi 的取值只有 0 或 1 两种情况，xi=1 表示第 i 个集装箱装入轮船，xi=0 表示第 i 个集装箱不装入轮船。

求解的问题可形式化描述为：


即求装入轮船的集装箱的最大数量。在从根结点出发搜索问题的解时，需要考虑两个约束条件：
1) 可行性约束条件：


2) 最优解约束条件：remain+cw>bestw，其中，remain 表示剩余集装箱的重量，cw 表示当前已装上的集装箱的重量，bestw 表示当前的最优装载量。

对于不满足约束条件的情况：


则剪去该分支。判定第 i 层的结点是否装入轮船的条件为：


当 cw(i)>c 时，表示该分支上的所有结点均不满足约束条件，应剪去该分支。若对于当前正在搜索的结点来说，沿着当前的结点继续向下扩展到叶子结点，就是将剩下的集装箱都装入轮船，总重量仍然不会大于当前的最优值 bestw，则没有必要对该结点的子树进行扩展，应剪去该分支结点。

若当前的扩展结点为第 i 个结点，则剩下的结点表示集装箱的重量为：


该结点代表集装箱的重量上界为 cw(i)+r。

若输入仍然是 c=50、W={18, 25, 25}，则解空间树的搜索过程如下图所示：


初始时、cw=0、bestw=0、r=68，然后考察第 1 个集装箱，此时有 cw=0、bestw=0、r=50，由于cw+w[1]<c，因此可选取第 1 个集装箱，在选取第 1 个集装箱后，进入解空间树的第 2 层，即开始考察是否将第 2 个集装箱装入轮船。

考察第 2 个集装箱，此时有 cw=18、bestw=0、r=25，由于 cw+w[2]<50，因此可选取第 2 个集装箱，在选取第 2 个集装箱后，就进入解空间树的第 3 层，即开始考察是否将第 3 个集装箱装入轮船。

考察第 3 个集装箱，此时有 cw=43、bestw=0、r=0，由于 cw+w[3]>50，因此第 3 个集装箱不能装入轮船。于是往右子树方向走下去，即不装入第 3 个集装箱，到达叶子结点，有 cw=43、bestw=43，找到一个解 {1,1,0}。

经过剪枝后的子集树如下图所示：


算法实现如下：

import java.util.Scanner;

class BestNode {
    int bestw;
    int[] bestx;
    final int NUM = 20;
    BestNode() {
        bestw = 0;
        bestx = new int[NUM];
    }
    int getBestW() {
        return bestw;
    }
    void setBestW(int cw) {
        bestw = cw;
    }
    void setBestX(int[] x) {
        for (int i = 0; i < x.length; i++) {
            bestx[i] = x[i];
        }
    }
    int getBestX(int i) {
        return bestx[i];
    }
}

public class ContainerLoading  {
    void Backtrack(int t, int n, int[] w, int c, int r, int cw, BestNode bNode, int[] x) {
        if (t >= n) { // 达到叶子结点
            if (cw > bNode.getBestW()) { // 若存在更优的解，则更新最优解
                bNode.setBestW(cw);
                for (int i = 0; i < x.length; i++) {
                    bNode.bestx[i] = x[i];
                }
            }
            return;
        }
        if (cw + w[t] <= c) { // 尝试放入当前集装箱
            x[t] = 1;
            cw += w[t];
            Backtrack(t + 1, n, w, c, r - w[t], cw, bNode, x);
            cw -= w[t]; // 回溯，恢复状态
            x[t] = 0;
        }
        Backtrack(t + 1, n, w, c, r, cw, bNode, x); // 不放入当前集装箱，继续尝试下一个
    }

    public static void main(String[] args) {
        final int NUM = 100;
        BestNode bNode = new BestNode();
        ContainerLoading  CL = new ContainerLoading ();
        int c, n, r, cw;
        int[] w;
        int[] x;
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入轮船的装载容量: ");
        c = sc.nextInt();
        System.out.print("请输入集装箱的数量: ");
        n = sc.nextInt();
        w = new int[n];
        x = new int[n];
        System.out.print("请分别输入" + n + "个集装箱的重量: ");
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }
        cw = 0;
        r = 0;
        for (int weight : w) {
            r += weight;
        }
        CL.Backtrack(0, n, w, c, r, cw, bNode, x);
        System.out.println("最优装载量: " + bNode.getBestW());
        System.out.print("装入轮船的集装箱编号: ");
        for (int i = 0; i < n; i++) {
            if (bNode.getBestX(i) == 1) {
                System.out.print(" " + (i + 1));
            }
        }
        System.out.println();
    }
}

程序运行结果如下：

请输入轮船的装载容量：65
请输入集装箱的数量：3
请分别输入3个集装箱的重量：42 10 21
最优装载量：63
装入轮船的集装箱编号：1 3

未到达叶子结点时，对该结点的两个分支分别进行处理。对于左孩子结点，若能装入轮船，也就是 cw+w[t]≤c 的情况，则令 x[t]=1、cw+=w[t]，表示为左分支结点，装入轮船，然后继续处理下一层，即递归调用自身。代码如下：

if (cw + w[t] <= c) { // 搜索图片文字内容搜索左子树
    x[t] = 1;
    cw += w[t];
    Backtrack(t + 1, n, w, c, r, cw, bNode, x);
    cw -= w[t]; // 恢复状态
}

对于右孩子结点，即不能装入轮船时，也就是 cw+w[t]>c 的情况，令 x[t]=0，表示为右分支结点，不装入轮船，然后继续处理下一层，即递归调用自身。代码如下：

if (cw + r > bNode.getBestW()) { // 搜索按钮文搜索右子树
    x[t] = 0;
    Backtrack(t + 1, n, w, c, r, cw, bNode, x);
}