背包问题 | Qi

背包问题是动态规划领域中一个重要且经典的问题，涉及在限定容量的背包中如何选择物品，使得物品的总价值最大化或总重量最小化。主要有两类背包问题：0-1背包问题和完全背包问题。

0-1背包问题：每个物品要么被选择一次，要么不选。
完全背包问题：每个物品可以被选择无限次。

以下是背包问题的一般步骤：

定义状态：通常使用一个二维数组 dp[i][j]，其中 dp[i][j] 表示前 i 个物品在背包容量为 j 时的最优解（价值或重量）。
状态转移方程：对于每个物品，可以选择将其放入背包（如果容量允许），也可以选择不放入。状态转移方程通常为：
1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
其中 weight[i] 表示第 i 个物品的重量，value[i] 表示第 i 个物品的价值。
边界条件：初始时，当没有物品可选时，dp[0][j] 都应为 0，当背包容量为 0 时，dp[i][0] 也都为 0。
计算顺序：通常从小规模问题开始，逐步计算出大规模问题的最优解。

下面是一个0-1背包问题的 Java 代码示例：

public class KnapsackProblem {
    public int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][capacity];
    }

    public static void main(String[] args) {
        KnapsackProblem knapsackProblem = new KnapsackProblem();
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;
        int maxValue = knapsackProblem.knapsack(weights, values, capacity);
        System.out.println("Maximum value: " + maxValue);
    }
}

在这个示例中，我们使用动态规划解决了0-1背包问题。通过遍历每个物品和背包容量，根据状态转移方程计算在当前情况下的最优解。最终，dp[n][capacity] 就是问题的最优解，表示在前 n 个物品中选择放入容量为 capacity 的背包所能获得的最大价值。

请注意，背包问题的动态规划解法也可能因为问题的具体要求而有所变化，但通常都涵盖了上述的状态定义、状态转移方程和边界条件。