Multiple Knapsack using Dynamic Programming

Question

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.

Answer 1

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