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 in a reasonable amount of time (aka not brute forcing every possible combination)? I am unfamiliar with dynamic programming but is this something better suited to that or is there a different technique I can use?
Very interesting problem! Yes, this problem can be solved with dynamic programming.
To understand how to solve, you first need to understand how knapsack is solved using dynamic programming: http://en.wikipedia.org/wiki/Knapsack_problem.
You can see that recursive function solving Knapsack has only one argument, that is remaining weight. To modify your problem you would need to "drag" along three more argument, which are storing how close to fulfilling each of compartment's conditions we are. Recursive function would therefore have 4 arguments.
Hope this helps.