0-1背包问题动态规划代码

A：

背包问题是一种经典的动态规划问题。0-1背包问题中，给定一个背包容量和一些物品，每件物品有一个重量和一个价值。需要选择一些物品放入背包中，使得在背包容量限制下总价值最大。

以下是0-1背包问题的动态规划代码。

def knapsack(w, v, C):
    # w: 物品的重量
    # v: 物品的价值
    # C: 背包容量
    n = len(w)
    # 初始化dp数组，dp[i][j]表示前i个物品，背包容量为j时的最大价值
    dp = [[0] * (C + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(C + 1):
            if w[i - 1] <= j:
                # 背包能够装下第i件物品
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
            else:
                # 背包装不下第i件物品
                dp[i][j] = dp[i - 1][j]
    
    return dp[n][C]

其中，dp[i][j]表示前i个物品，背包容量为j时的最大价值。

在每次计算dp[i][j]时，可以进行以下两种选择：

1. 不选择第i个物品，此时dp[i][j] = dp[i-1][j]；

2. 选择第i个物品，并将其放入剩余容量为j-w[i]的背包中，此时dp[i][j] = dp[i-1][j-w[i]] + v[i]。

两种选择中，选择最大价值的情况即可。

最终结果为dp[n][C]，表示前n个物品，背包容量为C时的最大价值。