0-1背包问题的回溯算法Java

以下是0-1背包问题的回溯算法Java代码实现：

public class KnapsackBacktracking {

    private int maxWeight = 0;
    private boolean[] bestSolution;
    private int[] weights;
    private int[] values;
    private int capacity;

    public int knapsack(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
        bestSolution = new boolean[weights.length];
        backtracking(0, 0, 0, new boolean[weights.length]);
        return maxWeight;
    }

    private void backtracking(int i, int weight, int value, boolean[] solution) {
        if (i == weights.length || weight == capacity) {
            if (value > maxWeight) {
                maxWeight = value;
                System.arraycopy(solution, 0, bestSolution, 0, solution.length);
            }
            return;
        }
        if (weight + weights[i] <= capacity) {
            solution[i] = true;
            backtracking(i + 1, weight + weights[i], value + values[i], solution);
        }
        solution[i] = false;
        backtracking(i + 1, weight, value, solution);
    }

    public boolean[] getBestSolution() {
        return bestSolution;
    }
}

其中，`knapsack()`方法接收物品重量数组`weights`、价值数组`values`和背包容量`capacity`，并返回最大价值。`backtracking()`方法是递归函数，用来搜索所有可能的解，并更新最优解。`maxWeight`和`bestSolution`分别用来保存最大价值和最优解。在递归过程中，如果当前重量或价值已经达到最大值，则结束递归。否则，对于每个物品，我们可以选择将其放入背包或不放入，分别递归求解。最后，通过`getBestSolution()`方法来获取最优解。