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?
