title: Dynamic T-SQL approach for combinatorics/knapsack
body: <p>I guess my question has to do with a variant of the knapsack problem, but I can't really come up with a solution for this:</p>
  
  <p>Let's say you are in a hardware store and need to buy 21 screws.
  They only offer them in bags:</p>
  
  <ul>
  <li>Bag X - 16 Screws - 1.56$ per screw - 25$ Total</li>
  <li>Bag Y - 8 Screws - 2.25$ per screw - 18$ Total   </li>
  <li>Bag Z - 4 Screws - 1.75$ per screw - 7$ Total   </li>
  </ul>
  
  <p>Now you have to figure out which Bags you should buy to get your 21 screws (or more!) for the lowest possible price.</p>
  
  <p>So what I got is a table with all the bags and a variable to define the required amount. What I need as a result should be a table with the bagname and the required amount.</p>
  
  <p>Unfortunately sqlfiddle is down.. But at least here's the example data:</p>
  
  <pre><code>declare @bags table (id int, qty int, price decimal(19,4))
  insert into @bags values
   (10, 16, 25.00)
  ,(20, 8, 18.00)
  ,(30, 4, 7.00)
  
  declare @ReqQty int = 21
  </code></pre>
  
  <p>I really appreciate your help! Hope we can get this solved, as I need to customize our companys ERP System with this important function.</p>
  
  <p>Thank you in advance!</p>
  
  <p>Edit:
  I read the whole wikipedia article about knapsack and there it says:
  <strong>Overfill approximation algorithm</strong>
  It may be possible to generate an approximation algorithm where we can slightly overflow the allowed weight limit. You would want to achieve at least as high a total value as the given bound B, but you're allowed to exceed the weight limit...
  <strong>Currently the solution is unknown for this approximation algorithm.</strong></p>
  
  <p>So it seems I better use a greedy algorithm instead of inventig the wheel? ;)</p>