背包问题代码Python

背包问题是计算机科学中经典的动态规划问题，通常涉及选择物品放入背包以最大化总价值，同时满足重量限制。在Python中，可以使用递归或迭代的方式来解决0-1背包问题（每个物品只能取一次）或完全背包问题（每个物品可以取任意多次）。这里是一个基本的0-1背包问题递归解决方案：

def knapsack(weights, values, capacity, n):
    # 创建一个表格来存储已计算的结果
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # 递归填充表格
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# 示例：给定重量 [50, 40, 60], 价值 [100, 90, 120] 和背包容量 100
weights = [50, 40, 60]
values = [100, 90, 120]
capacity = 100
n = len(weights)
max_value = knapsack(weights, values, capacity, n)

print("最大价值:", max_value)

在这个代码中，`dp[i][j]` 表示在前i个物品中选取总重量不超过j的情况下，能得到的最大价值。然后根据当前物品是否能装入背包，更新结果。