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

一尘不染

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

algorithm

在一个背包的情况下，用于最优填充背包的动态编程算法效果很好。但是，是否有一种有效的已知算法可以最佳地填充2个背包（容量可能不相等）？

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

首先使用原始的DP算法填充第一个背包，以填充一个背包，然后填充另一个背包。
首先填充大小为W1 + W2的背包，然后将解决方案分为两个解决方案（其中W1和W2是两个背包的容量）。

问题陈述（另请参阅维基百科的背包问题）：

我们必须用一组物品填充背包（每个物品都有一个权重和一个值），以便在总重量小于或等于背包尺寸的同时最大化从物品中获得的价值。
我们不能多次使用一个项目。
我们不能使用项目的一部分。我们不能拿一件东西的零头。（每个项目都必须完全包含在内）。

阅读 228

2020-07-28

共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背包的最大重量。请注意，如果容量很大，这不是很有效。

2020-07-28