2个填充背包的最佳方式？(Optimal way of filling 2 knapsacks?)

动态规划算法，以优化填充背包一个背包的情况下，效果很好。 但有一个有效的已知算法，将填补最佳背包2（容量可以不等）？

我曾尝试以下两种方法和他们都不是正确的。

1. 首先使用原来的DP算法来填充一个背包，然后填写其他背包填满第一背包。
2. 第一填充尺寸W1 + W2的背包，然后将溶液分成两个解决方案（其中，W1和W2是两个背包的能力）。

问题陈述（见背包问题在维基百科）：

1. 我们必须填补背包与一组项目（每个项目都有一个权重和值），从而最大限度地提高，我们可以从项目同时具有小于或等于背包的大小，总重量获得的价值。

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

3. 我们不能用一个项目的一部分。 我们不能把一个项目的一小部分。 （每个项目必须是完全包括或不包括）。

Answer 1:

我将承担每个的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是背包所能承载的最大重量。 请注意，这是不是很有效，如果容量变大。

Answer 2:

原来DP假定您的DP数组中标记出的值，你可以在背包获取和更新由因而考虑的元素来完成。
在2个背包情况可以使用2维动态数组，所以DP [i] [j] = 1时，可以把重量i到第一和重量J确定第二背包。 更新类似于原来的DP情况。

Answer 3:

递归公式有人正在寻找：

考虑到n个项目，这样的项目我有重量无线和值PI。 两个背包havk W1和W2的能力。

对于每一个0 <= I <= N，0 <= A <= W1，0 <= B <= W2，表示M [I，A，B]的最大值。

用于<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-无线] + PI}

每一个问题的解决与我的项目无论是在背包1个项目我在背包2，或没有。

文章来源: Optimal way of filling 2 knapsacks?