灌装2背包的最佳方法是什么？ [英] Optimal way of filling 2 knapsacks?

问题描述

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

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

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

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

1. 我们有填充背包与一组项目（每个项目的重和一个值），以最大限度地提高，我们可以从物品，同时具有总重量小于或等于得到的值背包的大小。

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

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

解决方案

我会假设每个 N 项目只能使用一次，而且必须最大限度地提高您的利润

原装背包是 DP [I] =最好的利润，你可以重得我

 对于i = 1到n做
  为W = maxW下降到[我]。重量做
    如果DP [W]＆LT; DP [瓦特 -  A [1]。重量] + A [1] .gain
      DP [W] = DP [W  -  A [1]。重量] + A [1] .gain
 

现在，因为我们有两个背包，我们可以使用 DP [I，J] =最好的利润，你可以重我的背包1和j背包2获得

 对于i = 1到n做
  对于W1 = maxW1下降到[我]。重量做
    为W2 = maxW2下降到[我]。重量做
      DP [W1，W2] = MAX
                   {
                       DP [W1，W2]，＆LT;  - 我们已经为这对一个不错的选择
                       DP [W1  -  A [1]。重量，西二环] + A [1] .gain＆LT;  - 放在背包1
                       DP [W1，W2  -  A [1]。重量] + A [1] .gain＆LT;  - 放在背包2
                   }
 

时间复杂度为 O（N * maxW1 * maxW2），其中 maxW 是最大权重的背包能携带。注意，这不是非常有效，如果容量变大。

The dynamic programming algorithm to optimally fill a knapsack works well in the case of one knapsack. But is there an efficient known algorithm that will optimally fill 2 knapsacks (capacities can be unequal)?

I have tried the following two approaches and neither of them is correct.

1. First fill the first knapsack using the original DP algorithm to fill one knapsack and then fill the other knapsack.
2. First fill a knapsack of size W1 + W2 and then split the solution into two solutions (where W1 and W2 are the capacities of the two knapsacks).

Problem statement (see also Knapsack Problem at Wikipedia):

1. We have to fill the knapsack with a set of items (each item has a weight and a value) so as to maximize the value that we can get from the items while having a total weight less than or equal to the knapsack size.

2. We cannot use an item multiple times.

3. We cannot use a part of an item. We cannot take a fraction of an item. (Every item must be either fully included or not).

解决方案

I will assume each of the n items can only be used once, and you must maximize your profit.

Original knapsack is 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

Now, since we have two knapsacks, we can use 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
                   }

Time complexity is O(n * maxW1 * maxW2), where maxW is the maximum weight the knapsack can carry. Note that this isn't very efficient if the capacities are large.

这篇关于灌装2背包的最佳方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！