0/1 Knapsack Problem Dynamic Programming

Given a bag which can only take certain weight W. Given list of items with their weights and price. How do you fill this bag to maximize value of items in the bag.

[bugra]

After 8 years, still so much better than our computer science teachers. Thank you for the video.
-Turkey

[touching-fish-technologist]

I finally see it, 2 years after I learnt my algorithm class. Thank you.

[cityandsuburb]

Thank you Mr. Roy, I cannot express just how important it has been to find your upload...
Gus,
London.

[gretacwink]

This is the THIRD video I've watched on the Knapsack problem and the ONLY one that helped me understand it. Thank you so much for sharing this!

[RanveerAggarwal]

Nicely put! Thanks for the explanation. It's great that you take an example and go through the problem step by step. Keep up the good work! :)

[FinanceStoryTime]

Amazing videos man. Like Sal Khan (founder of Khan academy), you have a unique knack for teaching extremely complex concepts. I have learnt so much from your videos. Thank you once again!!

[MegaChi]

Best 0/1 Knapsack tut on the Internet! Keep up the good work! :)

[AirTimeEh]

For those who are having trouble understanding how the table is generated; for me it helped the most to carefully listen from 8:15 to about 8:45

[AmanRaturi]

It's far better than 90% videos available on the same topic + you cover the basics... Keep up the good work !🤘

[lovisharora]

@Tushar Roy, we need more teachers like you. Your virtues: your videos are well paced unlike many other indian videos, which keeps a person interested, no extraneous content -- everything is precise and to the point (extremely helpful) at times while revising concepts. I wish you all the best for your future endeavours. Wish I could meet you some day personally for your autograph. Thanks a lot for your efforts, you are just amazing!! :)

[TheDeepsz]

I spent 2 whole days trying to understand 0-1 knapsack problem until I stumbled upon this video. This video explains more than just arriving on a mathematical equation. Many thanks for making this video.

[WinCPP]

Best tutorial on the 0-1 knapsack problem that I ever saw. Thanks!

[kaushikmondal]

Very nice, became a fan of you. best online teacher I have ever found. plz keep making video like this, the new generation student will be benefited.. Thank you..

[VivekHajela]

Hey Tushar, Many many thanks for doing such a wonderful job of explanining dynamic programming problems in such a lucid way!!. Kudos to you. However in your videos I find one little thing missing and thats is how you arrive at the optimal substructure property of a given example ( which IMO is the crux for nailing down new dyn problems). Like you directly start solving the probem by drawing a 2D /1D array, process of filling the array and then writing down the recurrence at the very end. It would be really helpful if you could spend time in discussing the thorught process to approach the problem first which will really help listeners to develop a knack of solving new dyn problems. As a very specific example, in this video , before even we start to solve the knapsack problem, discussing the optimal substructure property linguistically  like :

The maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

would have been really useful.

Thanks again for such a wonderful job!!

[PantMal]

For the people who are saying they didn't understand the tut: I had the same problem at first. I watched the video again a couple of times and now it all makes sense. Trust me, the more you watch the video the more sense it makes.

[alexanderdishes]

Tushar, THANK YOU!!!!

This was a great explanation. I wish my class material was as clear as this.

[LeviNotik]

Great video. The way you draw out the tabulation and go through it very clearly is very helpful.

[HarmanJat]

Thanks a lot for explanation.. I finally understood the algorithm.

I have just one suggestion, you should have 0th column also so that you have its row(top row) with all 0s.I got little bit lost :) with your explanation when you said for the first column with weight 1 that best we can do is 1 (for weight 0 to 7). If you had the top row (with 0s) you could have applied the max formula and shown everyone why each value ended up being 1 (like you did with other three items). The reason I mentioned this is because while writing a computer program we need the top row with 0s in order to make the max formula work for 1st item.

But again thanks a lot.. :)

[mimososo]

Thanks Tushar Roy for your simple way in teaching and your best way in delivering the main idea of the Algorithm

[andreis]

This is the exact same problem I got on my final algorithmics exam. God bless you!