# help with knapsack problem please!!

Printable View

• 01-16-2012, 05:47 PM
unimaasdreamteam
help with knapsack problem please!!
Hello everyone !

I'm working on the 0-1 knapsack problem for uni, and I have to fill a truck with a set of boxes, composed of 3 kinds each of them with different shape/volume and value, maximizing the total value of the load.

I have already implemented an algorithm using dynamic programming and memoizing/backtracking (it's actually a tree search which remembers previous nodes) which works pretty well for small sets of boxes (20-25 boxes) and reducing the cargo space of the truck as well (to around 20 cubic meters).

The problem is that the original truck has an available volume of 165 cubic meters, and the set of boxes can go up to 140 (let's say 64 boxes of kind A, 54 of kind B and 22 of kind C) so the algorithm takes way too long. I still don't have an answer and the other day I let the program run for 1 hour.
I have also tried to divide the truck in 4 pieces (dividing it into more smaller pieces wouldn't make sense) and tried to fill them separately, but still takes too long.

I was wondering if anyone have an idea about how to solve this problem, maybe something I could incorporate to my algorithm to optimize it and make it faster, or maybe a complete different method.

Thanks for the help in advance!!