2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Multiple Knapsack" - state the actual problem. $\endgroup$ – gnasher729 Jun 20 '17 at 15:59
  • $\begingroup$ I thought it was simple to image since knapsack problem is well known. Anyway, done! $\endgroup$ – André Gomes Jun 20 '17 at 17:06
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.