填充两个背包的最佳方法是什么？

Question

填充两个背包的最佳方法是什么？

algorithmdynamic-programminggraph-algorithmknapsack-problem

17

对于一个背包，动态规划算法可以有效地实现最优填充。但是是否有已知的高效算法可以最优地填充两个背包（容量可以不同）？

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

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

问题陈述（也可以在维基百科上查看背包问题）：

我们必须用一组物品（每个物品具有重量和价值）填满背包，以便在总重量小于或等于背包大小的情况下最大化从物品中获得的价值。
我们不能多次使用一个物品。
我们不能使用部分物品。我们不能取物品的一部分。（每个物品必须完全包括或不包括）。

- Nikunj Banka

“我已经尝试过”实际上意味着“在[算法：设计与分析，第2部分]（https://lagunita.stanford.edu/courses/course-v1:Engineering+Algorithms2+SelfPaced/about）课程中有人问了我这个问题”。当人们只关注自己时，真是让人爱不释手。 - Abhijit Sarkar

3个回答

1

原始的DP算法假定您在dp数组中标记可以在背包中获得的值，并通过相应地考虑元素来进行更新。
如果有两个背包，则可以使用二维动态数组，因此当您可以将重量i放入第一个背包和重量j放入第二个背包时，dp [i] [j] = 1。更新与原始DP情况类似。

- Grigor Gevorgyan

1

这对于超过2个背包是否可行？n个背包呢？ - Essej

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或两个背包都不放。

- sheldonzy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

我将假设这 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是背包可以承载的最大重量。请注意，如果容量很大，则效率不高。