The 0/1 Knapsack Problem - Dynamic Programming Method

The Dynamic Programming method to solving the 0/1 Knapsack Problem.

Note: I uploaded the wrong version cos I'm an idiot. There are three bugs.

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.

Category:

Education

Tags:

• Computer
• Science
• Source
• Knapsack
• Problem
• Dynamic
• Programming
• Algorithms
• Data
• Structures
• Imperative
• Zero
• One
• 0/1
• Array
• Keep
• Matrix
• Lecture
• Primer
• Introduction
• Mindez
• Video
• Explanation
• Description
• Educational

[daftp27]

Thank you :)..you remind me of Sheldon Cooper.

[Mindez]

@daftp27 Bazinga.

[hatsuharu333]

thanks - this helps a lot! I have a question though - when you check if there is any space to fit another item, do you check for the maximum at that weight for rows above the current row? for examle if you're in row 3, and you have 2 weight units left over, do you check row 0, 1, and 2 (or maybe just row 2?) to check for the most you could fit?

[Mindez]

@hatsuharu333 There cannot be a case where the number is higher further up. The highest number will always be in row 2. This is because when we populated row 2, we asked 'Is the number above bigger?' and if it was, we replaced it with that number. So we only need to check row 2, because it will ALWAYS be the maximum at that weight for the rows above the current row.

[SaudadeSunday]

What about the case where values do not matter? That is, if we only cared about filling up the knapsack to it's capacity or as close to it as possible? The answer for your particular example would be items one and two, in this case. But how would I go about finding this out using dynamic programming?

[Mindez]

@SaudadeSunday You could still model it like this, but set the values equal to the weights. That way you're trying to maximize the weights (ie. fit as much into the knapsack as you can), and everything has the same value/weight ratio so it's all about how much you can fit into the knapsack rather than how valuable it is.

[baggouras]

Thanks for the great explanation! :)

[daCorasla]

I didn't get the ending until I saw the comments you added about the video bugs. Cheers man, NOW it makes perfect sense.

Bazinga!

[cagripesek]

adamsın!adamın dibisin!

[J3joooo3]

thank you , that was so helpful

[miscul74]

Thank you ... really

[gmehlinf]

Cheers man, helped a lot !

[OasisDrinker0]

Cheers for reminding me of KILBURN