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!

Advertisements

5 Responses to Dynamic Programming – Solving The Knapsack Problem

  1. Shaun says:

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

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

  3. Gareth Mok says:

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

    Your failing at simple maths towards the end was entertaining 🙂

  4. Haha I can’t remember that – hope I cleared it up. Thanks for the comment! 🙂

  5. Matt Drumm says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: