背包问题python代码

当然，下面是一个使用动态规划解决背包问题的Python代码示例：

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] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])

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

    return dp[n][capacity], selected_items[::-1]

# 示例用法
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_value, selected_items = knapsack(weights, values, capacity)
print("最大价值:", max_value)
print("选择的物品:", selected_items)

这段代码使用了动态规划思想来解决背包问题。其中，`weights`是物品的重量列表，`values`是物品的价值列表，`capacity`是背包容量。函数`knapsack`返回最大的总价值和被选中的物品列表。

希望这个代码能帮到你！如果你还有其他问题，请随时问我。