algorithm - 背包多重约束

Question

我有一个动态规划问题，我花了几个小时研究但无济于事。

第一部分很简单:您有一背包元素，您必须最大化这些元素的值(value)，同时将它们保持在一定重量以下。

问题的第二部分是一样的，只是现在还有一个项目限制。例如:

在重量和元素限制下值(value)最大化的情况下，您可以放入包中的元素的最大值是多少？

我不知道如何实现这个问题的第二部分，我正在寻找一个通用算法。

Answer 1

在动态规划中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]

现在，当您添加项目限制时，您必须为每个项目选择最大值、值(value)、使用的项目数量来自

• 如果元素重量 <= 重量限制，重量和 n 件元素的值(value)，包括元素
• 重量值和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 件元素放入重量限制以下，如果不能，则相应地减少元素限制。