Multiple Knapsack using Dynamic Programming Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m &lt;= n), with


pj: profit of item j
wj: weight of item j
ci: capacity of bag i 


select m disjoint subsets of items so that the total profit of the selected items is a maximum, and each subset can be assigned to a different bag whose capacity is no less than the total weight of items in the subset.



I'm wondering if there is a reasonable way of solving MKP using DP. I get the point in 0-1 Knapsack Problem. The recurrence is quite straightforward, add item/ not add item.

dp[item][capacity] = max{
     value[item] + dp[item - 1][capacity - weight[item]],
     dp[item - 1][capacity]}

However, I cannot see how to get an recurrence equation for the MKP. Should I extend the recurrence equation to "add item bag 1/ not add item bag 1/ add item bag 2/ not add item bag 2" and so on and so forth? It does not seem a good approach as the number of bags becomes larger and larger.
When all values are 1 and all capacities the same, this is the bin-packing problem, which is Strongly NP-Complete. Therefore, a sensible DP solution is probably not possible unless P=NP.

For very small m, say m=3, you can do:

dp[item][capacity1][capacity2][capacity3] = max{
     value[item] + dp[item - 1][capacity1 - weight[item]][capacity2][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2 - weight[item]][capacity3],
     value[item] + dp[item - 1][capacity1][capacity2][capacity3 - weight[item]],
     dp[item - 1][capacity1][capacity2][capacity3]}