# Multiple Knapsack using Dynamic Programming

Def MKP (Multiple Knapsack Problem): Given a set of n items and a set of m bags (m <= 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.

• "Multiple Knapsack" - state the actual problem. Jun 20, 2017 at 15:59
• I thought it was simple to image since knapsack problem is well known. Anyway, done! Jun 20, 2017 at 17:06

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]}