1. 问题描述 用回溯法编写一个Java递归程序解决如下装载问题：有 n 个集装箱要装上 2 艘载重分别为 c1 和 c2的轮船，其中集装箱 i 的重量为 wi（1≤ i ≤ n），且∑ 𝑤𝑖 ≤ 𝑐1 + 𝑐2 𝑛 𝑖=1 。问是否有一个合理 的装载方案可以将这 n 个集装箱装上这 2 艘轮船？如果有，请给出装载方案。 举例：当 n=3，c1=c2=50，且 w=[10,40,40]时，可以将集装箱 1 和 2 装到第一艘轮船上， 集装箱 3 装到第二艘轮船上；如果 w=[20,40,40]时，无法将这 3 个集装箱都装上轮船。 输入格式 输入的第一行整数c，第一艘轮船载重量。 以后两行分别为每个集装箱的重量 输出格式 输出2行，第一行包含一个整数，表示最大载重量 接下来依次输出装入的集装箱序号 样例输入 10 w[]={0,3,5,6,8}; 样例输出 最大载重量为：9 构造最优解 :0 1 0 1 0

以下是一种可能的Java递归程序实现：

import java.util.Arrays;

public class ShipLoadingProblem {
    public static void main(String[] args) {
        int c1 = 50, c2 = 50;
        int[] w = new int[] {0, 10, 40, 40}; // 输入集装箱重量
        int n = w.length - 1; // 集装箱数量

        int[] x = new int[n + 1]; // 解向量
        int[] bestx = new int[n + 1]; // 最优解向量
        int bestw = 0; // 最优载重量

        backtrack(1, c1, c2, w, x, bestx, bestw); // 从第一个集装箱开始回溯搜索

        System.out.println("最大载重量为：" + bestw);
        System.out.print("构造最优解：");
        for (int i = 1; i <= n; i++) {
            System.out.print(bestx[i] + " ");
        }
    }

    // 回溯搜索函数
    private static void backtrack(int i, int c1, int c2, int[] w, int[] x, int[] bestx, int bestw) {
        int n = w.length - 1;
        if (i > n) { // 达到叶子节点，检查当前解是否更优
            if (c1 + c2 > bestw) { // 如果当前载重量更大，更新最优解
                bestw = c1 + c2;
                System.arraycopy(x, 1, bestx, 1, n); // 复制解向量
            }
            return;
        }
        if (w[i] <= c1) { // 尝试将集装箱i装到第一艘轮船上
            x[i] = 1;
            backtrack(i + 1, c1 - w[i], c2, w, x, bestx, bestw); // 继续搜索下一个集装箱
            x[i] = 0; // 恢复现场
        }
        if (w[i] <= c2) { // 尝试将集装箱i装到第二艘轮船上
            x[i] = 2;
            backtrack(i + 1, c1, c2 - w[i], w, x, bestx, bestw); // 继续搜索下一个集装箱
            x[i] = 0; // 恢复现场
        }
    }
}

这个程序的思路是使用回溯法搜索所有可能的集装箱装载方案，每次尝试将一个集装箱装到第一艘或第二艘轮船上，如果装载后仍满足重量限制，则继续搜索下一个集装箱。当搜索到叶子节点时，如果当前载重量更大，则更新最优解。由于每个集装箱只有两种选择，所以搜索树的深度是$n$，而每个节点有两个子节点，所以搜索时间复杂度为$O(2^n)$。但是，在实际问题中，可以使用剪枝等优化技巧来减少搜索空间和时间复杂度。