赞
踩
目录
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]
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。最后将最大价值和选中的物品打印出来。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。