背包算法python

背包算法（Knapsack Problem）是一种经典的优化问题，在Python中可以使用动态规划（Dynamic Programming）的方法来解决。它的基本思想是给定一组物品，每个物品有自己的价值和重量，目标是在不超过背包容量的情况下，选择总价值最大的物品组合。

在Python中，你可以按照以下步骤编写背包算法：

1. 定义数据结构：创建一个二维列表，其中每个元素表示物品的价值和重量，以及当前状态下是否放入该物品。

2. 动态规划：创建一个同样大小的数组用于存储最优解，初始值设为0。遍历所有物品，对于每个物品，考虑两种情况：放入和不放，根据这两个选择中的最大价值更新最优解数组。

3. 更新规则：对于每个物品i和背包容量w，如果物品重量小于等于当前容量，就取两者中的较大者作为新的最优解；如果物品重量大于当前容量，就不放入物品，直接保留之前的最优解。

4. 最终结果：当遍历完所有物品，最优解数组的最后一个元素就是最大价值。

def knapSack(weights, values, capacity):
    n = len(values)
    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(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][capacity]

# 示例
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(knapSack(weights, values, capacity))  # 输出最大价值