Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m <= n), withpj: profit of item jwj: weight of item jci: 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.
Multiple Knapsack using Dynamic Programming
np complete;dynamic programming;np hard;knapsack problems