title: Knapsack with selection from distinct groups
body: <p>I have a variation on the Knapsack Problem that I'm struggling to find an efficient solution for.</p>
  
  <p>Let's say you have multiple groups of items.  Each group can have an arbitrary number of items, each with a value and weight.  The problem is to find the set of items with maximum total value, weight &lt; some limit, and (the tricky part) only sets than include one item from EVERY group are valid.</p>
  
  <p>That is, imagine you have hundreds of items to pick from, but you must take one sandwich, one beverage, one snack, one flashlight, etc. Not just that you can't take more than one from any group, but you must at the end of the day end up with exactly g total items if there are g groups.</p>
  
  <p>It seems like this should be faster to do than the basic problem, because so many combinations are invalid, but I'm struggling to find a solution.</p>