Python代码动态规划求解完全背包问题

以下是 Python 代码实现完全背包问题的动态规划求解：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity+1)
    for i in range(n):
        for j in range(weights[i], capacity+1):
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
    return dp[capacity]

其中，`weights` 是物品重量的列表，`values` 是物品价值的列表，`capacity` 是背包容量。

代码逻辑如下：

1. 初始化一个长度为 `capacity+1` 的数组 `dp`，表示背包容量为 `j` 时，能够获得的最大价值。
2. 对于每一个物品 `i`，从重量为 `weights[i]` 开始循环到背包容量 `capacity`，计算在当前背包容量下能够获得的最大价值。
3. 最后返回 `dp[capacity]`，表示背包容量为 `capacity` 时，能够获得的最大价值。

示例：

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 输出：14

以上代码实现了完全背包问题的动态规划求解，时间复杂度为 $O(nC)$，其中 $n$ 是物品数量，$C$ 是背包容量。