我有一个动态编程问题，我花了几个小时研究无济于事。
第一部分很简单：你有一个背包，里面装着物品，你必须最大化这些物品的价值，同时将它们保持在一定的重量以下。
问题的第二部分是一样的，只是现在还有一个项目限制。 所以例如：
您可以放入袋子中的物品的最大价值是多少，以便在重量和物品限制下实现价值最大化？
我不知道如何实现这个问题的第二部分，我正在寻找一种通用算法。
在没有项目限制的动态编程解决方案中，您有 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]
现在，当您添加项目限制时，您必须为每个项目，值，使用的项目数量选择最大值 三元组
- 重量和 n 个项目的值，包括项目，如果项目重量 <= 重量限制
- 重量值和 n 项(不包括项(
为了表示项目数，您只需将第三个维度添加到先前使用的矩阵中，该矩阵表示已使用的项目数：
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
请注意，您可以稍微优化有关内存消耗的示例，因为在将第 z 项添加到解决方案时，您只需要知道 z - 1 项的解决方案。您还可以检查是否可以首先将 z 个项目放在重量限制下，如果没有，则相应地减少项目限制。