algorithm - 填充 2 个背包的最佳方式？

Question

最佳填充背包的动态规划算法在一个背包的情况下效果很好。但是是否有一种有效的已知算法可以最佳地填充 2 个背包(容量可能不相等)？

以下两种方法我都试过，都不对。

1. 先用原来的DP算法填充第一个背包，填充一个背包，然后再填充另一个背包。
2. 首先装满一个大小为 W1 + W2 的背包，然后将解分成两个解(其中 W1 和 W2 是两个背包的容量)。

问题陈述(另见维基百科的 Knapsack Problem):

1. 我们必须用一组元素(每个元素都有重量和值(value))装满背包，以便在总重量小于或等于背包的大小。

2. 我们不能多次使用一个项目。

3. 我们不能使用项目的一部分。我们不能拿走一件元素的一小部分。 (每个项目都必须完全包含或不包含)。

Answer 1

我将假设每个 n 项目只能使用一次，并且您必须最大化您的利润。

原始背包是 dp[i] = 重量 i 可以获得的最大利润

for i = 1 to n do
  for w = maxW down to a[i].weight do
    if dp[w] < dp[w - a[i].weight] + a[i].gain
      dp[w] = dp[w - a[i].weight] + a[i].gain

现在，因为我们有两个背包，我们可以使用 dp[i, j] = 背包 1 中的重量 i 和背包 2 中的重量 j 可以获得的最佳利润

for i = 1 to n do
  for w1 = maxW1 down to a[i].weight do
    for w2 = maxW2 down to a[i].weight do
      dp[w1, w2] = max
                   {
                       dp[w1, w2], <- we already have the best choice for this pair
                       dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1
                       dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2
                   }

时间复杂度是O(n * maxW1 * maxW2)，其中maxW是背包可以承载的最大重量。请注意，如果容量很大，这不是很有效。