python解决背包问题

背包问题是一个经典的组合优化问题，可以使用动态规划来解决。下面是一个简单的 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(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    selected_items = []
    w, c = n, capacity
    while w > 0 and c > 0:
        if dp[w][c] != dp[w - 1][c]:
            selected_items.append(w - 1)
            c -= weights[w - 1]
        w -= 1

    return dp[n][capacity], selected_items

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

max_value, selected_items = knapsack(weights, values, capacity)
print("Maximum value:", max_value)
print("Selected items:", selected_items)

在上面的代码中，我们定义了一个名为 `knapsack` 的函数，它接受三个参数：`weights` 是物品的重量列表，`values` 是物品的价值列表，`capacity` 是背包的容量。函数使用动态规划的方法计算出背包能够容纳的最大价值，并返回最大价值以及被选择的物品的索引列表。

在示例中，我们定义了一个背包容量为 8，有 4 个物品的例子。每个物品有对应的重量和价值。运行代码后，将输出最大价值为 11，并且被选择的物品的索引列表为 [3, 2]，表示选择了第 4 个物品和第 3 个物品。你可以根据自己的需求调整 `weights`、`values` 和 `capacity` 的值来尝试不同的背包问题实例。