title: 01 Knapsack specialization
body: <p>Excuse me if this has been answered already, but I don't have a deep knowledge of algorithms and don't always notice the subtleties between different specializations of the algorithms.  I have (what I think is) a slight variant of the 01-Knapsack problem.  I have a knapsack that has max weight W, and there are N items to choose from that have a weight w and value v.  What I want to do is maximize the total value, V, without going over W.  </p>
  
  <p>Classic Knapsack.  </p>
  
  <p><strong>Here's the twist</strong>: Of the items, I need to make sure that I have certain amounts (not up-to, but <strong><em>exact</em></strong> amounts) taken from different categories.  </p>
  
  <p>So lets assume that we have categories</p>
  
  <ul>
  <li>F - Food items</li>
  <li>T - Toys</li>
  <li>C - Clothes</li>
  <li>M - Miscellaneous (F, T, or C)</li>
  </ul>
  
  <p>I'm going on a 2 day trip, so I need to take 2 Food items, 1 toy to amuse the kid, and 2 items of clothes.  And as a kicker, I can take one additional item that is either a F, T OR C.  Note that every item is unique and can be included only once.</p>
  
  <p>From all of algos I've found, it seems like it's a hybrid of the 01 (unique items) and the bounded variant, though in the classic bounded knapsack we are binding the number of times we can include a particular item vs a particular <strong>category</strong></p>
  
  <p>If someone could point me to the right algorithm that'd be greatly appreciated. Bonus points for code in a "normal" language, and extra points if the implementation allows me to view the top n-number best results (you know, in case the optimal solution includes the toy that I just REALY can't stand or has 2 outfits that clash with each other).</p>
  
  <p>EDIT: Note that I want to be able to go on longer trips eventually, so I'm looking at taking 8-10 items total and the categories can have up to 250 or so items (that kid has way too many toys).  I can do some optimizations to reduce <em>some</em> of the items in each category (I'm really not going to take the ugly hawaiian shirt), but I can't reduce it enough to make a straight brute force implementation feasible. </p>