动态规划——使用python解决01背包问题

目录

什么是01背包问题？

        01背包问题是一个经典的组合优化问题，通常用于描述如下情境：假设有一个背包，它能够承受一定的重量上限（即背包容量），同时有一组物品，每件物品有自己的重量和价值。问题的目标是决定如何选择装入背包的物品，使得装入的物品的总价值最大，并且不能超过背包的承重上限。

        在01背包问题中，每件物品要么被完全装入背包（即选中），要么不被装入背包。这就是为什么它被称为“01”背包问题，其中“01”表示对每个物品的选择只有两种状态。这种限制条件使得问题具有一定的复杂性，需要采用动态规划等方法来解决。

         因此，01背包问题是一个经典的组合优化问题，它在实际生活中有着广泛的应用，例如在资源分配、投资决策等领域中都能够找到具体的应用案例。

题目：

       假设你有一个背包，它的容量是有限的。有一些物品，每个物品都有自己的重量和价值。你的任务是选择物品，将它们放入背包中，使得背包的重量不超过其容量，同时最大化背包中物品的总价值。

示例：

        假设你有一个承重量为W的背包，同时有n件物品和它们的重量数组weights[]以及价值数组values[]。请编写一个程序，找出能够装入背包的最大总价值，并输出这个最大总价值。

输入格式：

输入物品的数量：n

输入第一个物品的重量和价值（请使用空格分隔开）：x1  y1

输入第二个物品的重量和价值（请使用空格分隔开）：x2  y2

输入第三个物品的重量和价值（请使用空格分隔开）：x3  y3

…………………

输入第 n 个物品的重量和价值（请使用空格分隔开）：xn  yn

输出格式：

最大价值：

选中的物品：

代码实现：

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 w in range(1, capacity + 1):
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])

    selected = []
    w, v = capacity, dp[n][capacity]
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected.append(i)
            w -= weights[i - 1]

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

# 输入数据
n = int(input("请输入物品的数量: "))
weights = []
values = []
for i in range(n):
    weight, value = map(int, input("请输入第{}个物品的重量和价值（空格分隔）: ".format(i + 1)).split())
    weights.append(weight)
    values.append(value)
capacity = int(input("请输入背包的容量: "))

# 求解01背包问题
max_value, selected_items = knapsack(weights, values, capacity)

# 输出结果
print("最大价值:", max_value)
print("选中的物品:", [item for item in selected_items])

代码执行示例：

输入：

输出：

代码解析：

这段代码实现了一个解决01背包问题的动态规划算法。

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 w in range(1, capacity + 1):
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])

    selected = []
    w, v = capacity, dp[n][capacity]
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected.append(i)
            w -= weights[i - 1]

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

1. 输入参数：weights（物品的重量），values（物品的价值），capacity（背包的最大容量）。
2. 初始化一个二维列表dp，用于存储每个物品在不同重量限制下可以获得的最大价值。这个列表的每个元素dp[i][j]表示在前i个物品、重量限制为j的情况下可以获得的最大价值。所有元素初始化为0。
3. 两个嵌套循环遍历每个物品和每个可能的重量限制。如果第i个物品的重量weights[i-1]大于当前的重量限制w，那么选择这个物品无法提高总价值，因此dp[i][w] = dp[i-1][w]。否则，需要在不选择第i个物品（dp[i-1][w]）和选择第i个物品（dp[i-1][w-weights[i-1]] + values[i-1]）之间做出选择，取二者中较大的值作为dp[i][w]的值。这样可以保证在给定前i个物品和重量限制w的情况下，dp[i][w]的值总是非负的且是最大的。
4. 初始化一个空列表selected，用于存储被选中的物品的索引。同时初始化变量w和v，分别表示当前的重量限制和在给定前n个物品和重量限制capacity下可以获得的最大价值。
5. 反向遍历物品列表，从最后一个物品开始向前遍历。如果当前物品的加入能够提高总价值（dp[i][w] != dp[i-1][w]），则将当前物品的索引添加到selected列表中，并更新重量限制w。这样可以确定在给定前i个物品和重量限制w的情况下被选中的物品。
6. 返回在给定前n个物品和重量限制capacity下可以获得的最大价值dp[n][capacity]和被选中的物品的索引列表selected[::-1]，其中[::-1]表示逆序输出列表。
7. 算法的时间复杂度是O(nC)，其中n是物品的数量，C是背包的最大容量。

n = int(input("请输入物品的数量: "))
weights = []
values = []
for i in range(n):
    weight, value = map(int, input("请输入第{}个物品的重量和价值（空格分隔）: ".format(i + 1)).split())
    weights.append(weight)
    values.append(value)
capacity = int(input("请输入背包的容量: "))

# 求解01背包问题
max_value, selected_items = knapsack(weights, values, capacity)

# 输出结果
print("最大价值:", max_value)
print("选中的物品:", [item for item in selected_items])

通过主程序，输入物品数量n，再使用for循环，依次输入每个物品重量weights，物品价值values，最后再输入背包的容量capacity，再调用knapsack函数，将函数的返回值dp[n][capacity]即可得到背包能够容纳的最大价值，通过回溯的方式确定选中的物品。从最后一个物品开始，如果dp[i][w]不等于dp[i-1][w]，则说明选择了第i个物品，将其索引加入selected列表，并且更新背包容量w。最后将最大价值和选中的物品打印出来。