Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total number of total items that MUST be placed in each compartment of the backpack. Red Compartment MUST have 2 red items, Green Compartment MUST have 3 green items and the blue compartment MUST have 3 blue items. My backpack can hold some kind of max weight. I need to optimize for the max value given some weight.

To solve this problem I attempted to use the branch and bound technique used for solving the 0/1 backback. This technique computes quickly but picks items that leave too much left over space and doesn't return the optimal items.

What techniques can be used to solve this problem? I am unfamiliar with dynamic programming but is this something better suited to that or is there a different technique I can use?

  • $\begingroup$ For a general answer, see our reference question. $\endgroup$ – Raphael Apr 15 '15 at 9:03
  • $\begingroup$ You can always try exhaustive search... $\endgroup$ – Yuval Filmus Apr 16 '15 at 6:17

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.