ITC2009: Knapsack

The 5th problem of the Intel Threading Challenge 2009 Contest is a bounded knapsack  problem with real numbers instead of integers. You can get more information about knapsack problems in “Knapsack Problems: Algorithms and Computer Implementations”, Silvano Martello and Paolo Tooth, which is a free book.  I implemented a classical dynamic programming algorithm using Intel Threading Build Blocks to parallelize it. More information on dynamic programming in “Introduction to Algorithms, Second Edition” .

The approach I took to solve the problem is really naive due time constraints. The problems I found were:

  • Convert a bounded knapsack problem to a 0-1 knapsack problem.
  • Convert real number weights and benefits to integers.
  • Parallelization of the serial algorithm.
  • Memory efficiency.

The serial algorithm is really naive:

  1. Convert the weights and values to integer numbers.
  2. Convert the problem to a 0-1 knapsack problem repeating bounded limit times the items.
  3. Solve 0-1 knapsack problems with a dynamic programming algorithm.
  4. Trace back the items.

As you see this approach is the classical example of dynamic programming you can find in textbooks. Although it has big problems when you try to solve big data.  Repeating the items bounded limit times its a really easy way to convert the problem but needs tons of memory. Multiplying by 100 makes the deal, but it can lead to rounding precision problems. The parallel algorithm is the same but using a “parallel_for” to replace the second for loop of the algorithm.

Well, the solution proposed is very naive, so I don’t expect good results in the contest. Anyway, I enjoyed the problem and I’m already thinking about the next one: “Segment intersection”.

Comments are closed.