I have a few knapsacks of given capacities.

Also, much more items of given weights and values.

As usual, items have to be put into knapsacks to maximize profit.

What is different from a standard MKP, is that there’s a requirement that each knapsack has to be filled completely. I.e. the sum of weights of its items has to be equal to its capacity (while in the standard problem, it is less-than-equal).

How to approach this? (I want to find an algorithm to solve this.)

  • $\begingroup$ What are you trying to do ? Show that it is NP-Complete ? Find an algorithm to solve it ? $\endgroup$ – GBat Jan 12 at 13:52
  • $\begingroup$ @GBat Oh, right, sorry! To find an algorithm. =) $\endgroup$ – Michal Rus Jan 12 at 20:56

Your Answer

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

Browse other questions tagged or ask your own question.