在动态规划中solution http://www.geeksforgeeks.org/knapsack-problem/如果没有项目限制,您将拥有 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)))
Output:
Max value for weight limit 5, no item limit: 7
Max value for weight limit 5, item limit 2: 5
请注意,您可以在内存消耗方面对示例进行一些优化,因为将第 z 项添加到解决方案时,您只需要知道 z - 1 项的解决方案。此外,您还可以检查是否可以将 z 件物品放入重量限制以下,如果不能,则相应地减少物品限制。