填充2背包的最佳方式？

Question

在一个背包的情况下,用于最佳地填充背包的动态编程算法很好地工作.但是,是否有一种有效的已知算法可以最佳地填充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背包可以承载的最大重量.请注意,如果容量很大,则效率不高.