0/1 knapsack problem dynamic programming | explained step by step

The 01 Knapsack problem is one of the most asked computer programming problems. It is often asked in the interviews of big tech companies like Google, Amazon and Adobe.
In this video, we will solve the knapsack problem using dynamic programming.

What is knapsack problem?

let's a say I am a thief and I have a bag of capacity 5 kgs.
I break into a shop and find only 5 items of different weights each of which is less than 5 kgs.

Consider the weights of the individual items be [4,2,3,1] which have values as [18, 20, 11, 22]

So, I as a thief have to pick those items for which the combined weight comes out to be equal to or less than 5 kgs for which I get the maximum value.

The solution to Knapsack problem described above is going to 42 which I will get when I chose items of weights [2,1] kgs.

I believe you have to got the gist of the problem now, so let's watch this video of Joey'sTech to learn solving the 0/1 knapsack using Dynamic Programming.

[abhisheknagar]

Very Nicely explained...everyone trying to hone up their programming skills must watch this video

[chrisogonas]

Excellent illustration and clarity. Thanks Joey's Tech!