17

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

我尝试了以下两种方法，但它们都不正确。

  1. 首先使用原始的 DP 算法填充第一个背包，填充一个背包，然后填充另一个背包。
  2. 首先填充一个大小为 W1 + W2 的背包，然后将溶液分成两个溶液（其中 W1 和 W2 是两个背包的容量）。

问题陈述（另见Wikipedia 上的背包问题）：

  1. 我们必须用一组物品（每个物品都有一个重量和一个值）填充背包，以便在总重量小于或等于背包大小的情况下最大化我们可以从这些物品中获得的价值。

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

  3. 我们不能使用项目的一部分。我们不能拿走一件物品的一小部分。（每个项目都必须完全包含或不包含）。
4

3 回答 3

11

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

原来的背包是dp[i] = best profit you can obtain for weight 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] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2

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背包可以承载的最大重量在哪里。请注意，如果容量很大，这不是很有效。

于 2013-02-09T12:57:42.473 回答
1

原始 DP 假设您在 dp 数组中标记了您可以在背包中获得的值，然后通过考虑元素来完成更新。
如果有 2 个背包，您可以使用二维动态数组，因此dp[ i ][ j ] = 1当您可以将重量i放在第一个背包上，将重量j放在第二个背包上时。更新类似于原始 DP 案例。

于 2013-02-09T10:29:37.623 回答
1

递归公式是任何人都在寻找：

给定 n 个项目，使得项目 i 具有权重 wi 和值 pi。两个背包具有 W1 和 W2 的容量。

对于每一个 0<=i<=n, 0<=a<=W1, 0<=b<=W2，表示 M[i,a,b] 的最大值。

对于 a<0 或 b<0 - M[i,a,b] = -∞ 对于 i=0 或 a,b=0 - M[i,a,b] = 0

公式：M[i,a,b] = max{M[i-1,a,b], M[i-1,a-wi,b] + pi, M[i-1,a,b- wi] + pi}

i 项问题的每个解决方案要么在背包 1 中，要么在背包 2 中，要么在其中没有第 i 项。

于 2018-02-20T15:30:58.763 回答