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.
Problem statement (see also Knapsack Problem at Wikipedia):
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.
We cannot use an item multiple times.
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.