1. 问题描述 用回溯法编写一个递归程序解决如下装载问题：有 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代码

以下是Java代码实现：

import java.util.Scanner;

public class Main {
    static int n, c1, c2; // n个集装箱，c1和c2为两艘轮船的载重量
    static int[] w = new int[101]; // 存储每个集装箱的重量
    static boolean[] x = new boolean[101]; // 存储每个集装箱是否已经被放入轮船中
    static boolean flag = false; // flag表示是否已经找到解决方案

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        c1 = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        c2 = c1; // 第二艘轮船的载重量与第一艘相同
        n = w.length - 1; // 有效集装箱数量
        dfs(1, 0, 0); // 从第一个集装箱开始搜索
        if (!flag) { // 如果没有找到解决方案
            System.out.println("无法装载所有集装箱！");
        }
    }

    private static void dfs(int i, int cw1, int cw2) {
        if (flag) { // 如果已经找到解决方案了
            return;
        }
        if (i == n + 1) { // 如果已经搜索完所有集装箱
            if (cw1 + cw2 <= c1 + c2) { // 如果所有集装箱的重量小于等于两艘轮船的载重量之和
                System.out.println("最大载重量为：" + (cw1 + cw2));
                System.out.print("构造最优解：");
                for (int j = 1; j <= n; j++) {
                    if (x[j]) { // 如果第j个集装箱已经被放入轮船中
                        System.out.print("1 ");
                    } else {
                        System.out.print("0 ");
                    }
                }
                System.out.println();
                flag = true; // 标记已找到解决方案
            }
            return;
        }
        if (cw1 + w[i] <= c1) { // 如果第i个集装箱可以放入第一艘轮船中
            x[i] = true; // 标记第i个集装箱已经被放入轮船中
            dfs(i + 1, cw1 + w[i], cw2); // 搜索下一个集装箱
            x[i] = false; // 回溯，标记第i个集装箱没有被放入轮船中
        }
        if (cw2 + w[i] <= c2) { // 如果第i个集装箱可以放入第二艘轮船中
            x[i] = true; // 标记第i个集装箱已经被放入轮船中
            dfs(i + 1, cw1, cw2 + w[i]); // 搜索下一个集装箱
            x[i] = false; // 回溯，标记第i个集装箱没有被放入轮船中
        }
    }
}