0
我有一个动态编程问题,我花了几个小时研究无济于事。背包多种限制
第一部分很简单:你有一个背包物品,你必须最大化这些物品的价值,同时保持它们低于一定的重量。
问题的第二部分是相同的,除了现在还有一个项目的限制。例如:
您可以放入包中的物品的最大值是多少,以便在重量和物品限制下最大化该值?
我不知道如何实现这个问题的第二部分,林寻找一个通用算法。
我有一个动态编程问题,我花了几个小时研究无济于事。背包多种限制
第一部分很简单:你有一个背包物品,你必须最大化这些物品的价值,同时保持它们低于一定的重量。
问题的第二部分是相同的,除了现在还有一个项目的限制。例如:
您可以放入包中的物品的最大值是多少,以便在重量和物品限制下最大化该值?
我不知道如何实现这个问题的第二部分,林寻找一个通用算法。
在没有项目限制的动态编程solution中,您有2D矩阵,其中Y轴是项目索引,X轴是重量。然后,对于每个项目,重量对你选择重量的最大
之间下面是例如在标准溶液的Python:
def knapsack(n, weight, values, weights):
dp = [[0] * (weight + 1) for _ in range(n + 1)]
for y in range(1, n + 1):
for x in range(weight + 1):
if weights[y - 1] <= x:
dp[y][x] = max(dp[y - 1][x],
dp[y - 1][x - weights[y - 1]] + values[y - 1])
else:
dp[y][x] = dp[y - 1][x]
return dp[-1][-1]
现在,当您添加项目限制时,您必须为每个项目选择最大值,值,使用的项目数让我们从重量
价值为代表的项目的数量,你可以只添加第三维表示使用过的物品的数量之前使用的矩阵:
def knapsack2(n, weight, count, values, weights):
dp = [[[0] * (weight + 1) for _ in range(n + 1)] for _ in range(count + 1)]
for z in range(1, count + 1):
for y in range(1, n + 1):
for x in range(weight + 1):
if weights[y - 1] <= x:
dp[z][y][x] = max(dp[z][y - 1][x],
dp[z - 1][y - 1][x - weights[y - 1]] + values[y - 1])
else:
dp[z][y][x] = dp[z][y - 1][x]
return dp[-1][-1][-1]
简单的演示:
w = 5
k = 2
values = [1, 2, 3, 2, 2]
weights = [4, 5, 1, 1, 1]
n = len(values)
no_limit_fmt = 'Max value for weight limit {}, no item limit: {}'
limit_fmt = 'Max value for weight limit {}, item limit {}: {}'
print(no_limit_fmt.format(w, knapsack(n, w, values, weights)))
print(limit_fmt.format(w, k, knapsack2(n, w, k, values, weights)))
输出:
Max value for weight limit 5, no item limit: 7
Max value for weight limit 5, item limit 2: 5
请注意,您可以优化例如关于内存消耗一点,因为加入第i个项目,你只需要知道对于z解决方案的解决方案时 - 1项。你也可以检查是否有可能将z物品放在重量限制之下,并且如果不能相应地减少物品限制。
非常感谢!这是超级洞察力。我希望你是我的讲师! – fortune