Dynamic Programming – Solving The Knapsack Problem
May 19, 2010 5 Comments
How do we fit the most valuable items from a selection of items into a knapsack? This… ladies and gentlemen, is the Knapsack problem.
After hearing countless renditions of this algorithm and many conversations, I’ve decided to put a description of the algorithm together in a video. The video is 20 minutes in total. If you think that you get the idea earlier on, then do feel free to skip to the last part, which shows the completion of the dynamic programming tables and actually getting the answer.
Thanks to Dave Buckley for his explanations, and to Pete Sutton for the program shown in the videos.
Hope this helps!