0/1 Knapsack problem | Dynamic Programming

Overview of the 0/1 Knapsack problem using dynamic programming

Algorithms repository:

My website:

[cernsb]

Your repository of algorithms containing running times for each, and video explanations has been absolutely invaluable! Thanks so much!

[sallaklamhayyen]

simple + clear + concise explanation = thank you so much.
please continue ❤

[saadahmed]

Hi William, your graph theory playlist is awesome but your dp playlist has a flaw. These videos are explaining how the solutions to these problems work but not how one can use the general steps of dp to come up with these. I think the reason why dp is hard for most people is because of the pedagogy. I think dp should be taught by identifying sub-problems, showing the recurrence relationship between them and then how we can connect it all together to solve the problem. While looking at this, my brain tended to focus more on the visual aspect of how the table is being built instead of what every step is telling me to do. I hope I made my point clear. Thanks for making these videos for us for free. I'll pay it forward by making such videos myself when I have fully understood these concepts from ground up.

[davidmclean]

Thank you for giving us your time and sharing your knowledge.

[outofbody]

nice video but it doesn't really explain the intuition behind how one would achieve this solution

[abhirup]

I was having a really hard time with DP but it's so much easier to imagine the solution every dp problem as the shortest paths tree of a directed acyclic graph. so in this case it would follow the topological sort and ONLY update cell (or relax it) if DP's condition is met. In cases of actual graphs this is exactly what we do to find shortest paths tree for a DAG.

[nicolasbalandier]

Thank you so much for the clear explanations about how to know wich items are added to the knapsack.

[arihantparsoya]

Best explanation I have found so far. Thank you.

[kevinkkirimii]

Hi William be blessed highly, you have really educated me in alot programming concepts. Keep sharing your gift.

[harishshankar]

Crystal clear explanation! Appreciate your effort!!

[Himanshubishnoi-qgyg]

Thanks I understood that no possibility is missed, but in starting we think some possibility would be missed as we gave the first element priority over second, second over third!!

[andriicherevko]

With this third video (and two other previous) this theme has cleared up. Thanks to author!

[Himanshubishnoi-qgyg]

This was very simple and perfect explanation 🙏🙏

[nar]

5:10
Really confuses me because how does the algo know if the capacity is filled or not? Sure if I take dp[i-1][j], I take the one cell above and I know it fulills the capacity as well but at which point can the algorithm casually decide to include 2 items, repsectively x items in the KnapSack?

Like, in dp[2][4], we're talking about item 2 but for some reason we can fit in both in there because the weight limit is 4. Somewhere the algo kind of figured out that the weight limit was reduced to 1 because item 1 was inserted but because item 2 has weight 1, we can insert item 2 as well?

[Nope-hzux]

Why do you make your arrays 1 based? It seems like you just add a lot of confusion and make more work for yourself.

[JZX]

Beautiful explanation! Thanks a million times

[fakhrifajar]

Hi, I wanna ask, when you insert the value for the next cell (blue arrow) why it points to previous item (the diagonal arrow), instead you said that for the next cell we use the value of current item?

[KarmaBiting]

I think entries [4, 4] and [5, 4] should both be 5 instead of 6 in your example. [5, 6] should also be 8. Nonetheless, good video. I didn’t understand any solutions until this one, so thanks!

[yeger]

sei fortissmo fratè, thank u so much

[lesliengo]

Why is the first blue arrow is pointed at (0, 0)?