Java01背包问题实现回溯算法

以下是Java实现01背包问题的回溯算法的代码示例：

public class Knapsack {
    private int maxWeight = Integer.MIN_VALUE; // 背包能装的最大重量
    private int[] items; // 物品重量数组
    private int n; // 物品个数
    private int w; // 背包重量

    public void backTrack(int i, int cw) {
        if (i == n || cw == w) { // 装满了或者物品装完了
            if (cw > maxWeight) {
                maxWeight = cw;
            }
            return;
        }
        backTrack(i + 1, cw); // 不装第i个物品
        if (cw + items[i] <= w) { // 装第i个物品
            backTrack(i + 1, cw + items[i]);
        }
    }

    public int getMaxWeight(int[] items, int n, int w) {
        this.items = items;
        this.n = n;
        this.w = w;
        backTrack(0, 0);
        return maxWeight;
    }
}

其中，`backTrack`方法是回溯算法的核心实现，`getMaxWeight`方法是对外暴露的接口，用于获取背包能装的最大重量。