A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items).

We're having some trouble finding good references and existing implementations, mostly because I am not an expert in this area, but I ended up working with the student anyhow. I would appreciate some help with:

  1. What are some reasonable heuristic and/or approximation 0-1 knapsack algorithms that are not too complicated that the student could study? (References please.)

  2. Are there existing libraries which look for solutions or approximate solutions?

  • 2
    $\begingroup$ You might be interested in PAAL. On a quick look, they seem to have at least 3 different algorithm for solving (0/1) knapsack. They have literature references to the algorithms they have used as well. $\endgroup$ – Juho Feb 17 '15 at 7:55
  • 2
    $\begingroup$ I'd suggest you the book "Knapsack Problems" by Kellerer, Pferschy, Pisinger. It is a good introduction to this area and provides most of the common algorithms for exact and approximate solutions as well. $\endgroup$ – user1742364 Feb 17 '15 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.