Optimal way of filling 2 knapsacks?

问题:

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).

回答1:

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:

The original DP assumes you mark in the dp array that values which you can obtain in the knapsack, and updates are done by consequently considering the elements.
In case of 2 knapsacks you can use 2-dimensional dynamic array, so dp[ i ][ j ] = 1 when you can put weight i to first and weight j to second knapsack. Update is similar to original DP case.

回答3:

The recursive formula is anybody is looking:

Given n items, such that item i has weight wi and value pi. The two knapsacks havk capacities of W1 and W2.

For every 0<=i<=n, 0<=a<=W1, 0<=b<=W2, denote M[i,a,b] the maximal value.

for a<0 or b<0 - M[i,a,b] = −∞ for i=0, or a,b=0 - M[i,a,b] = 0

The formula: M[i,a,b] = max{M[i-1,a,b], M[i-1,a-wi,b] + pi, M[i-1,a,b-wi] + pi}

Every solution to the problem with i items either has item i in knapsack 1, in knapsack 2, or in none of them.