目录
什么是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背包问题的动态规划算法。文章来源：https://www.toymoban.com/news/detail-768058.html
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]
- 输入参数：weights（物品的重量），values（物品的价值），capacity（背包的最大容量）。
- 初始化一个二维列表dp，用于存储每个物品在不同重量限制下可以获得的最大价值。这个列表的每个元素dp[i][j]表示在前i个物品、重量限制为j的情况下可以获得的最大价值。所有元素初始化为0。
- 两个嵌套循环遍历每个物品和每个可能的重量限制。如果第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]的值总是非负的且是最大的。
- 初始化一个空列表selected，用于存储被选中的物品的索引。同时初始化变量w和v，分别表示当前的重量限制和在给定前n个物品和重量限制capacity下可以获得的最大价值。
- 反向遍历物品列表，从最后一个物品开始向前遍历。如果当前物品的加入能够提高总价值（dp[i][w] != dp[i-1][w]），则将当前物品的索引添加到selected列表中，并更新重量限制w。这样可以确定在给定前i个物品和重量限制w的情况下被选中的物品。
- 返回在给定前n个物品和重量限制capacity下可以获得的最大价值dp[n][capacity]和被选中的物品的索引列表selected[::-1]，其中[::-1]表示逆序输出列表。
- 算法的时间复杂度是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。最后将最大价值和选中的物品打印出来。文章来源地址https://www.toymoban.com/news/detail-768058.html
到了这里，关于动态规划——使用python解决01背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
