Algorithms – The 0/1 Knapsack Problem – Dynamic Programming method


Okay, I didn’t see that James had made a video about the very same subject. Great minds think alike I guess? Sigh. Well, here it is: The Dynamic Programming method for solving a 0/1 Knapsack Problem explained, in depth, by me in under 11 minutes!

Bug 1: Ignore the “The cell with the green circle around has a capacity of” blah blah etc. because I uploaded the wrong version ._. The green circle should be around cell (3,1).
Bug 2: I circle item ‘1’ when I should circle item ‘3’ at the end when we’re going through the keep array. I fail.
Bug 3: I say ‘2’ somewhere instead of ‘3’. See if you can spot it.

About these ads

5 Responses to Algorithms – The 0/1 Knapsack Problem – Dynamic Programming method

  1. Really good explanation man, and pretty different to mine too.

  2. Shaun says:

    I was worried for a second the weighted companion cube would have to be euthanised

  3. Mindez says:

    But the problem is that not all of the companion cubes will fit into the aperture science emergency intelligence incinerator. So what’s the greatest value of companion cubes that we can euthanise that will fit in the aperture science emergency intelligence incinerator?

  4. jsdhillon says:

    very nice expanation…thanks

  5. msohcw says:

    Much better than how I learnt it, thanks a lot ;)

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

Follow

Get every new post delivered to your Inbox.

Join 45 other followers

%d bloggers like this: