# 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.

Advertisements

### 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 😉