01背包问题动态规划py

下面是一个简单的 Python 代码实现 01 背包问题的动态规划算法：

def knapsack01(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 j < weights[i - 1]:
                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` 是物品重量列表，`values` 是物品价值列表，`capacity` 是背包容量。`dp` 是一个二维列表，`dp[i][j]` 表示前 `i` 个物品放入容量为 `j` 的背包中所能获得的最大价值。

该算法的时间复杂度为 $O(nC)$，其中 $n$ 是物品的数量，$C$ 是背包的容量。