title: Algorithm design: can you provide a solution to the multiple knapsack problem?
body: <p>I am looking for a pseudo-code solution to what is effectively the <a href="http://en.wikipedia.org/wiki/List_of_knapsack_problems" rel="noreferrer">Multiple Knapsack Problem</a> (optimisation statement is halfway down the page). I <em>think</em> this problem is NP Complete so the solution doesn't need to be optimal, rather if it is fairly efficient and easily implemented that would be good. </p>
  
  <p>The problem is this:</p>
  
  <ul>
  <li>I have many work items, with each taking a different (but fixed and known) amount of time to complete.  </li>
  <li>I need to divide these work items into groups so as to have the smallest number of groups (ideally), with each group of work items taking no longer than a given total threshold - say 1 hour. </li>
  </ul>
  
  <p>I am flexible about the threshold - it doesnt need to be rigidly applied, though should be close. My idea was to allocate work items into bins where each bin represents 90% of the threshold, 80%, 70% and so on. I could then match items that take 90% to those that take 10%, and so on.</p>
  
  <p>Any better ideas?</p>