Algorithm design: can you provide a solution to the multiple knapsack problem?

Question

I am looking for a pseudo-code solution to what is effectively the Multiple Knapsack Problem (optimisation statement is halfway down the page). I think 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.

The problem is this:

• I have many work items, with each taking a different (but fixed and known) amount of time to complete.
• 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.

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.

Any better ideas?

Answer 1

You need http://www.or.deis.unibo.it/knapsack.html, chapter 6.6 "Multiple knapscack problem - Approximate algorithms". There is pseudo-code (Pascal style) in the text and Fortran implementations (yes, it's an old book) as a ZIP file.

Answer 2

As far as I know, the problem is NP complete (Wikipedia confirms), so there's probably not much sense in attempting to solve it exactly. However, any number of approaches might be good enough for you: greedy, genetic algorithms, simulate annealing...greedy is probably the easiest to implement:

while (time available in block greater than smallest task duration)
  find the longest fitting task
  add it

...you get the idea.