algorithm - Complex 0/1 Backpack with multiple compartments -

say have 3 compartments in backpack: red, green, blue , 3 sets of items: red items, green items , blue items have weight , benefit. have requirement around total number of total items must placed in each compartment of backpack. red compartment must have 2 red items, green compartment must have 3 green items , blue compartment must have 3 blue items. backpack can hold kind of max weight. need optimize max value given weight.

to solve problem attempted use branch , bound technique used solving 0/1 backback. technique computes picks items leave left on space , doesn't return optimal items.

what techniques can used solve in reasonable amount of time (aka not brute forcing every possible combination)? unfamiliar dynamic programming better suited or there different technique can use?

very interesting problem! yes, problem can solved dynamic programming.

to understand how solve, first need understand how knapsack solved using dynamic programming: http://en.wikipedia.org/wiki/knapsack_problem.

you can see recursive function solving knapsack has 1 argument, remaining weight. modify problem need "drag" along 3 more argument, storing how close fulfilling each of compartment's conditions are. recursive function therefore have 4 arguments.

hope helps.