01背包一维空间py

"01背包问题"是一个经典的动态规划问题，它通常用于描述一种资源分配决策，比如你有一个容量有限的背包，可以装物品，每个物品有自己的重量和价值。在一维空间的Python实现中，我们通常是通过创建一个二维数组`dp`来记录状态，其中`dp[i][j]`表示前i个物品，总重量不超过j的情况下可以获得的最大价值。

算法步骤大致如下：
1. 初始化：`dp[0][0] = 0`，代表无物品时背包的价值为0。
2. 遍历物品：对于第i个物品，有两种选择：要么不放入背包（`dp[i][j] = dp[i - 1][j]`），要么放入背包（如果当前物品重量小于等于背包剩余容量，`dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight_i] + value_i)`）。
3. 最终结果：返回`dp[n][W]`，n为物品总数，W为背包容量。

以下是简单的Python代码示例：

def knapsack_01(items, W):
    n = len(items)
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]

    for i in range(1, n+1):
        for w in range(1, W+1):
            if items[i-1][0] <= w:  # 如果物品能放入背包
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i-1][0]] + items[i-1][1])  # 选或不选
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

items = [(60, 100), (100, 200), (120, 300)]
W = 500
print(knapsack_01(items, W))