背包问题回溯算法 java

以下是使用回溯算法解决背包问题的Java代码示例：

public class KnapsackProblem {
    private int maxWeight; // 背包的最大承重
    private int[] weight; // 物品的重量数组
    private int[] value; // 物品的价值数组
    private int[] selected; // 选中的物品数组
    private int maxValue; // 最大价值

    public KnapsackProblem(int maxWeight, int[] weight, int[] value) {
        this.maxWeight = maxWeight;
        this.weight = weight;
        this.value = value;
        this.selected = new int[weight.length];
        this.maxValue = 0;
    }

    public void backtrack(int i, int currentWeight, int currentValue) {
        if (i == weight.length) { // 已经遍历完所有物品
            if (currentValue > maxValue) { // 更新最大价值
                maxValue = currentValue;
                System.arraycopy(selected, 0, bestSelected, 0, selected.length); // 更新选中的物品数组
            }
            return;
        }
        if (currentWeight + weight[i] <= maxWeight) { // 如果当前物品可以放入背包
            selected[i] = 1; // 标记当前物品已选中
            backtrack(i + 1, currentWeight + weight[i], currentValue + value[i]); // 递归选择下一个物品
            selected[i] = 0; // 回溯，取消当前物品的选择
        }
        backtrack(i + 1, currentWeight, currentValue); // 递归不选择当前物品
    }

    public void solve() {
        backtrack(0, 0, 0);
        System.out.println("最大价值为：" + maxValue);
        System.out.print("选中的物品为：");
        for (int i = 0; i < bestSelected.length; i++) {
            if (bestSelected[i] == 1) {
                System.out.print(i + " ");
            }
        }
    }
}

其中，`maxWeight`表示背包的最大承重，`weight`表示物品的重量数组，`value`表示物品的价值数组，`selected`表示选中的物品数组，`maxValue`表示最大价值。`backtrack`方法是回溯算法的核心部分，其中`i`表示当前遍历到的物品编号，`currentWeight`表示当前已选中的物品的总重量，`currentValue`表示当前已选中的物品的总价值。在`backtrack`方法中，首先判断当前物品是否可以放入背包，如果可以，则将其标记为已选中，递归选择下一个物品；如果不可以，则直接递归选择下一个物品。当遍历完所有物品后，如果当前的总价值大于最大价值，则更新最大价值和选中的物品数组。最后，在`solve`方法中调用`backtrack`方法求解背包问题。