0-1背包 算法 python

0-1背包问题是一个经典的动态规划问题，其目标是在给定一组物品和一个背包容量的情况下，选择物品放入背包，使得放入背包的物品总价值最大化，同时保证总重量不超过背包容量。

下面是一个使用Python实现0-1背包算法的示例代码：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])
            else:
                dp[i][j] = dp[i-1][j]

    return dp[n][capacity]


# 示例用法
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

max_value = knapsack(weights, values, capacity)
print("最大价值：", max_value)

这段代码中，`weights`和`values`分别表示物品的重量和价值，`capacity`表示背包的容量。函数`knapsack`使用动态规划的方式计算出最大价值，并返回结果。

希望这个示例能够帮助你理解0-1背包算法的实现。