Geek Answers Handbook

Algorithm Design: Can you suggest a solution to the problem with multiple backpacks?

I am looking for a pseudo-code solution for what is effective. A problem with several backpacks (the optimization operator is halfway down the page). I think this problem is NP Complete, so the solution should not be optimal, and if it is sufficiently effective and easy to implement, it will be good.

The problem is this:

  • I have many work items, each of which takes a different (but fixed and known) amount of time to complete.
  • I need to divide these work elements into groups in order to have the least number of groups (ideally), and each group of work elements takes no more than a given common threshold - say, 1 hour.

I am flexible about the threshold - it does not need to be hard applied, although it should be close. My idea was to distribute work items into boxes, where each bit represents 90% of the threshold, 80%, 70%, etc. Then I could compare items that occupy 90%, for those that occupy 10%, etc.

Any better ideas?

+7
design algorithm knapsack-problem
source share
2 answers

You need http://www.or.deis.unibo.it/knapsack.html , chapter 6.6, "The problem with several knapscack - Approximate Algorithms". There is pseudocode (Pascal style) in Fortran text and implementations (yes, this is an old book) as a ZIP file.

+5
source share

As far as I know, the NP problem is complete (Wikipedia confirms ), so there is probably not much point in trying to solve it to the point. However, any number of approaches can be good enough for you: greedy, genetic algorithms that simulate annealing ... greedy are 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.

+1
source share

More articles:


All Articles