Solve the knapsack problem with 1,000 items and with a weight limit of 50, in less than a second, with weights and values given between 1 and 30. Only the optimal solution is acceptable!
- an evolutionary approach to solve an NP-hard/NP-complete problem,
- chromosome initialization via a greedy algorithm,
- elitist selection strategy,
- three different crossover strategies,
- extremely low memory usage,
- multithreaded computation,
- a lot of performance tweaks here and there,
- … in less than 200 lines of c++!
The algorithm uses ~1,1MB of memory for the 1,000 item, and still less than 3,5MB for the 10,000 item problem sets – compare it to the memory consumption of the dynamic programming approach of the problem. The average time needed to compute the optimum with 1,000 items and a limit of50 is 0.05s – that’s 1/20th of a second.
Download
Code
Feel free to fiddle around with the parameters to achieve better results at different, possibly harder problem sets!
