背包问题 递归实现 java 输出所有解

背包问题是一个经典的动态规划问题，递归是其中一种解法。我将使用Java编程语言实现递归解法来输出所有解。

首先，我们需要定义一个递归函数来解决背包问题。这个函数的参数包括背包的容量、物品的重量数组、物品的价值数组以及当前处理到的物品索引。

递归函数的实现如下所示：

public static void recursion(int capacity, int[] weights, int[] values, int index, ArrayList<Integer> result) {
    if (index >= weights.length || capacity <= 0) {
        // 输出当前解
        System.out.println(result);
        return;
    }

    // 不选择当前物品
    recursion(capacity, weights, values, index + 1, result);

    // 如果当前物品的重量小于等于背包容量，选择当前物品
    if (weights[index] <= capacity) {
        result.add(index);
        recursion(capacity - weights[index], weights, values, index + 1, result);
        result.remove(result.size() - 1);
    }
}

接下来，我们可以编写一个辅助函数来调用递归函数，传入相应的参数。

public static void printAllSolutions(int capacity, int[] weights, int[] values) {
    ArrayList<Integer> result = new ArrayList<>();
    recursion(capacity, weights, values, 0, result);
}

最后，我们可以在主函数中测试上述函数的结果。首先定义物品的重量和价值数组，然后调用`printAllSolutions`函数。

public static void main(String[] args) {
    int capacity = 10;
    int[] weights = {2, 3, 4, 5};
    int[] values = {3, 4, 5, 6};
    
    printAllSolutions(capacity, weights, values);
}

这样，程序将会输出所有的解，每一行是一个解，以列表的形式展示选中的物品索引。

希望这个回答能够帮助到您！