完全背包一维空间py

完全背包问题（0-1 Knapsack Problem）是一个经典的动态规划问题，在Python中可以使用一维数组来求解。这个问题涉及到在给定总重量限制下，选择物品使得总价值最大。以下是使用Python解决这个问题的一个基本步骤：

1. 初始化：创建一个大小为`weights+1`的列表（`weights`为物品的重量范围），并将所有元素初始化为0，表示当前状态（无物品）的最大价值。

2. 动态规划：遍历每个物品i，对于每个重量j（从0到总重量limit），检查是否能包含物品i。如果可以（即`weight[i] <= j`），则比较包括该物品的价值（`values[i] + dp[j-weight[i]]`）和不包括的价值（`dp[j]`）。取其中较大的作为新状态下的最大值，并将结果存储在`dp[j]`中。

3. 结果：最后，`dp[limit]`就是完全背包问题的答案，即在总重量限制下可以获得的最大价值。

def knapsack(weights, values, limit):
    n = len(weights)
    dp = [0] * (limit + 1)

    for i in range(1, n + 1):
        for j in range(weights[i - 1], -1, -1):  # 可以包含物品i的情况
            if j + weights[i - 1] <= limit:
                dp[j + weights[i - 1]] = max(dp[j + weights[i - 1]], dp[j] + values[i - 1])
            else:
                break

    return dp[limit]

# 示例
weights = [2, 3, 4, 5]
values = [6, 9, 7, 11]
limit = 10
max_value = knapsack(weights, values, limit)
print(f"最大价值是：{max_value}")