I wrote a solution using this table building DP algorithm a few years ago. https://github.com/mgraczyk/DiscreteOptimization/blob/master/knapsack/speed_up/s

I wrote a solution using this table building DP algorithm a few years ago. https://github.com/mgraczyk/DiscreteOptimization/blob/master/knapsack/speed_up/solve_it.cpp This was part of an assignment for a Coursera Discrete Optimization course created by The University of Melbourne. It's a great course and I recommend it to anybody who wants to hone their understanding of dynamic programming and solving computationally expensive problems. https://www.coursera.org/course/optimization