什么是0-1背包问题？

0-1背包问题是一种经典的组合优化问题，它的目标是在给定的一组物品中选择一些物品放入背包中，使得物品的总价值最大，同时要求背包的总容量不超过限定值。在0-1背包问题中，每个物品只能选择放入背包一次（即0或1），不能重复放入。

0-1背包问题可以用动态规划来解决。首先，我们定义一个二维数组dp，其中dp[i][j]表示在前i个物品中，背包容量为j时的最大价值。然后，我们可以通过以下状态转移方程来计算dp[i][j]的值：

- 如果第i个物品的重量大于背包容量j，则dp[i][j] = dp[i-1][j]，即不选择第i个物品；
- 如果第i个物品的重量小于等于背包容量j，则dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，即选择第i个物品或不选择第i个物品，取两者中的最大值。

最后，dp[n][C]即为问题的解，其中n为物品的个数，C为背包的容量。

下面是一个示例代码，演示了如何使用动态规划解决0-1背包问题：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value = knapsack(weights, values, capacity)
print("Max value: ", max_value)  # 输出：Max value:  9