Is this problem a knapsack problem?

What is a possible algorithm for the 0-1 Knapsack problem with 2 sacks?

• More formally, say, we have 2 sacks with capacities c1 and c2. There are N items with profits pi and weights wi. As in 0-1 Knapsack problem, we need to fill in c1 and c2 with these items in such a way the overall profit is maximized. Assume pi and wi are positive integers! Also, how much optimal solutions are there? (Since, there can be more than one solution because, if m1=m2, that straight away gives us 2 possible solution as the items in m1 and m2 can be interchanged. Another example would be when there are more than one item with same weight and profit).

• Answer:

  In the usual knapsack problem, we would define a variable best[i][j] as the maximum profit we could get from the first i items such that a total weight of exactly j was used. Here, we would have a variable best[i][j][k] instead : the maximum profit we could achieve from the first i items such that the weight of exactly j was used in knapsack #1 and a weight of exactly k was used in knapsack #2. This will solve the problem. For counting the number of ways, keep another variable cnt[i][j][k] : The number of ways of achieving a profit of best[i][j][k] from  the first i items such that the weight of exactly j was used in knapsack #1 and a weight of exactly k was used in knapsack #2. The DP is pretty easy to derive along with the knapsack DP.