以下是使用 Python 实现 01 背包问题的动态规划解法：
def knapsack_01(weights, values, capacity):
n = len(weights) # 物品数量
dp = [0] * (capacity + 1) # 初始化 dp 数组，容量为 0 到 capacity 的最大价值
for i in range(n):
# 注意这里是从后向前遍历，保证每个物品只被使用一次
for j in range(capacity, weights[i] - 1, -1):
# 如果当前背包容量 j 大于等于当前物品重量 weights[i]
# 则更新 dp[j]为放入该物品或不放入该物品的最大价值
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity] # 返回最大价值
# 示例
weights = [2, 3, 4, 5] # 物品重量
values = [3, 4, 5, 6] # 物品价值
capacity = 5 # 背包容量
max_value = knapsack_01(weights, values, capacity)
print("背包能装的最大价值为:", max_value)
在这个实现中，weights 和 values 是列表，分别表示每个物品的重量和价值。capacity 是背
包的最大承重。dp 数组用于存储每个容量下的最大价值。
外层循环遍历每个物品，内层循环则从背包容量 capacity 开始，向下遍历到当前物品的重量
减一。注意这里内层循环是倒序的，这是为了避免在计算 dp[j]时，使用到已经因为放入当
前物品而被更新过的 dp[j - weights[i]]值。
最后返回 dp[capacity]，即背包容量为 capacity 时的最大价值。
这个解法的时间复杂度是 O(n*capacity)，其中 n 是物品的数量，capacity 是背包的最大承重。
空间复杂度是 O(capacity)，因为只需要一个长度为 capacity+1 的数组来存储状态。
