回溯法求解最优装载问题java

回溯法是一种求解组合优化问题的常用方法，下面给出一个使用回溯法求解最优装载问题的Java代码示例：

public class Backtracking {
    private int n; // 集装箱数量
    private int[] w; // 集装箱重量
    private int c; // 轮船承载能力
    private int cw; // 当前载重量
    private int bestw; // 最优载重量
    private int r; // 剩余集装箱重量

    public int loading(int[] weight, int capacity) {
        n = weight.length;
        w = weight;
        c = capacity;
        cw = 0;
        bestw = 0;
        r = 0;
        for (int i = 0; i < n; i++) {
            r += w[i];
        }
        backtrack(0);
        return bestw;
    }

    private void backtrack(int i) {
        if (i >= n) {
            if (cw > bestw) {
                bestw = cw;
            }
            return;
        }
        r -= w[i];
        if (cw + w[i] <= c) {
            cw += w[i];
            backtrack(i + 1);
            cw -= w[i];
        }
        if (cw + r > bestw) {
            backtrack(i + 1);
        }
        r += w[i];
    }
}

使用示例：

int[] weight = {2, 2, 3, 1, 5, 2};
int capacity = 10;
Backtracking bt = new Backtracking();
int bestWeight = bt.loading(weight, capacity);
System.out.println("最优载重量为：" + bestWeight);

其中，`loading`方法接受一个整型数组`weight`和一个整数`capacity`，返回最优载重量。回溯法的核心部分在于`backtrack`方法，其中`i`表示当前处理的集装箱编号，`r`表示剩余集装箱重量。在每个集装箱上，分别尝试不装载和装载两种情况，然后递归处理下一个集装箱。如果当前载重量超过了最优载重量，则更新最优载重量。