title: Approach to a Bin Packing sql problem
body: <p>I have a problem in sql where I need to generate a packing list from a list of transactions.</p>
  
  <h2>Data Model</h2>
  
  <p>The transactions are stored in a table that contains:</p>
  
  <ul>
  <li>transaction id</li>
  <li>item id</li>
  <li>item quantity</li>
  </ul>
  
  <p>Each transaction can have multiple items (and coincidentally multiple rows with the same transaction id).  Each item then has a quantity from 1 to N.</p>
  
  <h2>Business Problem</h2>
  
  <p>The business requires that we create a packing list, where each line item in the packing list contains the count of each item in the box.  </p>
  
  <p>Each box can only contain 160 items (they all happen to be the same size/weight).  Based on the total count of the order we need to split items into different boxes (sometimes splitting even the individual item's collection into two boxes)</p>
  
  <p>So the challenge is to take that data schema and come up with the result set that includes how many of each item belong in each box.</p>
  
  <p>I am currently brute forcing this in some not so pretty ways and wondering if anyone has an elegant/simple solution that I've overlooked.</p>
  
  <h2>Example In/Out</h2>
  
  <p>We really need to isolate how many of each item end up in each box...for example: <br />
  <br />
  Order 1:
  <ul>
  <li>100 of item A</li><li>100 of item B</li><li>140 of item C</li></ul><br />
  This should result in three rows in the result set: </p>
  
  <ul>
  <li>Box 1: A (100), B (60) </li><li>Box 2: B(40), C (120) </li><li>Box 3: C(20)</li>
  </ul>
  
  <p><br />
  Ideally the query would be smart enough to put all of C together, but at this point - we're not too concerned with that.</p>