Tuesday 18 May 2010

Dynamic Programming - Solving The Knapsack Problem

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!

















5 comments:

  1. Thanks James that explained a lot...gotta love the screen recording feature in Snow Leopard lol

    ReplyDelete
  2. Yeaa man the features just keep coming! I wonder if we'll see the announcement of the next big cat on 7th June.

    ReplyDelete
  3. Excellent video James, your efforts are very much appreciated. Thank you!

    Your failing at simple maths towards the end was entertaining :)

    ReplyDelete
  4. Haha I can't remember that - hope I cleared it up. Thanks for the comment! :)

    ReplyDelete
  5. Yeh this cleared up the topic, Its nice to have a walkthrough

    ReplyDelete