The 0/1 Knapsack Problem - Dynamic Programming Method

[@ThisOneGoes211]

Great video, man. You explained dynamic programming very well! I had trouble visualizing the concept, and seeing it laid out in a grid like this really drove the point home.

[@MemoryException]

Ten years later and this video is still helping people! This is the best explanation I have seen of the Knapsack Problem.

[@Musathic495]

You can do it from the right instead. And when you do it from the right, you can actually just use the same row and overwrite it, instead of having a different row for every time you add a new item. Then, for the keep array, instead of storing 1 or 0, you'll store the weight of the item that was last used to reach there. So in the example he gives, the keep array would look like this after he finished: 1 1 3 3 1 And it would be "the last item we used had weight X" and then you backtrack.

[@Mnaircckel]

One of the best explanations for DP I've seen. Great!

[@BackToBackSWE]

I also cover this problem if you want deeper insight...been 2 years tho :)

[@LikeACrouton]

Thank you, man. Very clear explanation, easy to follow, and you've got a good voice for it to boot.

[@zoeywanderlust2358]

I did a variation of this problem in college in my "structures and algorithms" course. Now, at work, im trying to apply it to a business problem and have to explain my approach to my colleagues who dont have a background in CS after watch numerous videos to teach myself how to approach this problem, your method is by far the simplest and clearly and concise explains the problem - 10 mins; wow! It usually takes me an hour ... i go off on tangents about polynomials and pseudo-polynomials etc..

[@vikashrajasamuelselvin1948]

Clear and Concise and easy to translate into code. This is my Python implementation for the above: def knapsack(items,weights,maxWeight): # Create the V and Keep tables v = [ [0 for col in range(maxWeight+1)] for row in range(len(items)) ] keep = [ [0 for col in range(maxWeight+1)] for row in range(len(items)) ] # Build the V and Keep tables print "Printing the V table" print '0\t'*(len(v[0])-1) for i in range(1,len(v)): s = '' for j in range(1,len(v[0])): if j-weights[i] >= 0: if v[i-1][j-weights[i]] + items[i] > v[i-1][j]: keep[i][j] = 1 v[i][j] = max(v[i-1][j], v[i-1][j-weights[i]] + items[i]) else: v[i][j] = v[i-1][j] s += str(v[i][j]) + "\t" print s print "Maximum possible attainable sum = %s. " % (v[i][j]) # Printing the Keep table print "Printing the Keep table" for i in range(1,len(v)): s = '' for j in range(1,len(v[0])): s += str(keep[i][j]) + "\t" print s # Use the keep table to find which elements contributed to this path = [] while i > 0 and j > 0: if keep[i][j] == 1: path.append(i) j -= weights[i] i -= 1 else: i -= 1 print " The elements considered for maxsums : %s. " % ([items[x] for x in path]) def main(): # Define the input items = [ 0, 3, 1, 4, 103, 4, 5, 1, 6, 6 ] weights = [ 0, 1, 1, 1, 2, 2, 2, 3, 3, 3 ] maxWeight = 3 #items = [ 0, 5, 3, 4 ] #weights = [ 0, 3, 2, 1 ] #maxWeight = 5 knapsack(items,weights,maxWeight) if __name__ == '__main__': main()

[@alexfiuk6688]

The ONLY good explanation of DP I've encountered so far. Thank you so much.

[@Mackattack2294]

Thank you very much sir. For any other viewers, note the questions that he asks for each respective cell. Pause and replay portions until you catch the pattern. Once you catch the pattern this is trivial. Again thank you very much sir.

[@dmdque]

I watch this video every few years to refresh. Great explanation!

[@ifoundthewords]

Best explanation of 0/1 Knapsack Problem, also great demonstration of dynamic programming paradigm (breaking a problem into smaller versions of itself and using the solutions to the miniature problems to build up to the solution of the original problem)

[@williamb1933]

Best explanation on the internet - better than the MIT and coursera lecture. Thanks so much, made it crystal clear.

[@mohitshah8839]

Out of all the bloody explanations on the net this is the one i was able to understand. Buddy thank you really !!!!!!!!! Keep it up

[@pankajjoshi3302]

the best explanation on knapsack problem i have ever seen

[@ccario83]

Excellent video, very clearly explained. When defining the 0/1 knapsack problem, you mention that an item can only be wholly in or out of the knapsack and that items can't be split. You may also want to say that only one of each item can be used in total. This is subtle and implied, but important to explicitly state, otherwise people may wonder why 5 of item 3 isn't the optimal solution!

[@MoriturHostis]

Very good explanation, with a calm voice. Helped me a lot, thanks!

[@vietfoodhackers5866]

More like this please. This is the best 0-1 knapsack dynamic explanation on the web.

[@vj1824]

Super explanation. I watched other 3 videos on KZbin but did not understand DP. This is the best video which has explained it perfectly. Thank you!

[@franciscomcgee8105]

i've watched a ton of probs on this, including from MIT, Stanford, etc. your explanation is the best. my teacher didn't have the second table, but i like the way you included it, it helps me keep track of which ones to keep with the little algorithm for "W" and "I". very pro. you didn't go too fast at all. i didn't get lost because of the damned green circles in the wrong place. i did watch the video 5 times though, not because your explanation is flawed, but because the PROBLEM ITSELF is complicated.

[@gideonrichter4977]

Oh my god. I sat through 1.5h of universal confusion during a lectture and I reached understanding at 4:21. Wow, thanks.

[@jflaoeal]

Even if this was the wrong version this is still a very detailed way of describing the algorithm. Thank you.

[@Jeka2008]

I spent 2 days trying to understand my prof's notes..... Then I found your video and it took me 10 minutes to understand... Thank you very much!

[@piyushjaininventor]

you did mistake in the last step. you circled item 1 as item 3 with green circle. :P

[@TheNickparsa]

Thank you! you helped me a lot! 1st: we should know that we can use the item i to be in the knapsack or not. max{v(i-1),x OR v(i)+v(i-1),x-w(i)} if we want to use the item i then we should consider the remaining space that we may have to use so we would use the item i with value i and we would add the value of the item before and the capacity is the remaining which is the one you told us. OR we don't use the item i because when we use it hasn't a good high acceptable value and it just make knapsack heavy hmmm, I have exam tomorrow n I just understood something,thanks god

[@TheNickparsa]

Rafi mojabi :)

[@rifatulkarim261]

possibly the only youtuber manage to make us understood something interesting!

[@rodrigovieira1994]

Thanks for uploading this. I had trouble understanding the problem yesterday in class, you just helped me a lot. Subscribed!

[@colbybrown2870]

The first time I head about this, it was pronounced "oh one knapsack", which I misunderstood to be O(1)... I was rather confused by the possibility that knapsack could be solved in constant time. This makes much more sense.

[@scottkralph]

Very good explanation -- thanks. As others have noted, when scanning the keep array the circled values at the top left are not what you meant them to be

[@shreyamss3297]

Following lectures in class had only explained about memorizing the formula .this clip helped a lot bro .tanx mahn

[@SaudadeSunday]

@Mindez Thank you for the reply. I kind of answered my own problem in the comments right after I asked, but your reply is very much appreciated. Your entire video was well-done and your explanation of the concept is a life-saver.

[@kikogol182]

I've seen 5 explanations on youtube, this is one is the best by far

[@mushikuldeep1]

best explanation of dynamic knapsack problem

[@electric_boogaloo496]

When you go through the keep array to find the optimal solution, you mix up item 3 and 1.

[@TheHellbeas7]

Thank you! Really simple and elegant explanation of the solution! The best i have seen so far!

[@AhnafTabrez]

wow! you took only 10 minutes to make it crystal clear what my university couldn't do in 3 lectures :/ Thanks man! That was a great help. Now i am feeling like acing the exam tomorrow :D

[@hammett3]

great stuff man. Hope you keep doing it. I realize it's a lot of work and appreciate your effort.

[@juliansalama]

That's the best explanation of the knapsack problem.

[@SquaredMediaYT]

Thanks, helped a bunch. I'll be watching this again to make sure I got it down.

[@seaque.]

finally an explanation without a disturbing accent.

[@ypsyee7186]

Best explanation that I've ever seen + good pronunciation. Thanksssssss

[@pradhumns]

Awesome video. The best explanation of this problem on youtube. Hats off.. 

[@ifoundthewords]

Really great video! Thanks a lot for uploading! It's a tremendous help to have someone walk through every little tiny step of an algorithm.

[@eyestrikers]

Thanks a lot... Got exam tomorow and this was bothering me. Helped a lot. keep making videos like this.

[@vudejavudeja]

Thanks for your great knapsack walkthrough! I especially liked the companion cubes ;) Keep up the good work!

[@aakashpreetam7383]

Best 01 Knapsack DP Lecture

[@CocogoatGaming]

Very high quality. 10/10

[@TheKaratekidd32v]

not sure if this was said in a previous comment or not, but in the end when you go back through the keep table to see which items to put in the knapsack, I think you circle the wrong items so its a little hard to follow. When looking at I=3, W=5 and seeing a 1 in the keep table, the 1 should indicate the third item is being chosen, but the first item is circled. Hope this helps with anyone's confusion.

[@SaudadeSunday]

Ah, I suppose I could use the objects' weight as values, which would mean I would end up maximizing the value up to a limit of the weight, which is precisely what I want. Thanks for the advice! And the video!

[@andreffotografia]

wow, my professor should see how to teach it in 10 minutes and stop NOT teaching it in 2 hours. Thanks a lot, amazingly useful class :) Please post more computer science videos!

[@yashwanthsrini]

This is probably the best video on this. Thanks a lot.

[@shikharchauhan465]

I'm elated that you cut to the chase and explained the `how` of the problem rather than chasing around formulae.

[@Saurabh-fw5rm]

Although had to rewind few times,Its now crystal clear!! Thanks Mindez

[@MrLAduke12]

Good job bro, i get it thanks to you....If only my lecturers could get to the point and explain it like this.

[@danamuise4117]

excellent, thank you! I think instead of the "keep" table, you can just ask if [i][w] !=[i-1][w]

[@danieltriantafyllis3011]

It took me 5 videos to find you but it was worth it!

[@michaelgulak]

Thanks man. Your explanation was succinct but effective.

[@guerzo95]

Best explanation on internet, very clear, tanks man!!

[@harshalkutkar]

Thank you so much! You saved me from failing my exam!

[@rockon123451000]

*** in this example where there r 3 items with w={2,3,4} and v={1,2,5} weight of knapsack=6, when finding the value at [3][6], u have to add value 5 of item 3 to the item in the 2nd column in row 2 right..but its 0 so the value according to ur explanation at [3][6] should be 5. but with capacity 6 i could put item 3 and item 1 in it to make the value 5+1=6...jus look into this if u could.thanks for the explanation:)

[@littech4637]

Awesome video my friend. You should consider making more Computer related videos because your explanations are very clear.

[@ΜιχάληΓάμα]

I finally understood the knapsack problem! Thanks so much!

[@Musathic495]

I guess we should take a step back. This idea works for all numbers of additional constraints in that it reduces the dimension you need by 1. So for the original problem with only 1 constraint, you'll only need a 1 dimensional array. If you can understand that, then applying that idea to more constraints is relatively straightforward. It all depends on how you store the keep array, and how you iterate through the regular array. See how in the video, he iterates from the left? You can d

[@olapopoola6093]

Genius is the word! That's what you are man...

[@monaami555]

The best explanation that i have found. Could you please delete all the other videos about knapsack problem on youtube, they are just confusing people :P

[@MagicWinterNights]

Really good stuff, cleared everything that I needed, including the conquer part of the algorithm!

[@JoeRodrig3]

Great video man! I appreciate the work you put in to this.

[@reyou7]

best explanation on KZbin.

[@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?

[@shinythps]

Thank you, helped me a ton! I was struggling with this algoritmh, but now it's all good!

[@visweswaranr]

Fantastic explanation. Thank you for this. Very clear.

[@jagajugue]

Damn man! That was a awesome explanation. Thanks!

[@DJRevan]

Oh My goood! Thank you very much! I've been struggling with this for days!

[@gilly2891]

Best Video in 01 KP problem... Than you very much !!!

[@B3rwyn]

A great tutorial and explanation. Very well done!

[@777naufal]

PRAISE THE LORD, THANK YOU SO MUCH!

[@miso5037]

Sir , you are the best. Thank you very much. You explained very good.

[@chowsquid]

The last section was very confusing because you were going very fast and you circled item 1 when you were talking about item 3. Also, row "i" and column "w" isn't obvious since the column wasn't labelled. After rewinding a number of times, I was able to figure it out.

[@tintintintino]

your lecture is so intuitive, thanks!

[@adampatam]

Thank you so much!! I so appreciate good videos that make sense!

[@samansepehrpartopooy]

great job! that was one of the most helpful videos I've ever seen!

[@gabthebest99]

No, it only means that you either take an item or not, which means you can't take a fraction of the item. The bounded and unbounded stuff is about a maximum number of each items

[@TheSgtBeefheart]

Are you ever going to make more of these? This was VERY helpful.

[@ryshoooo1]

thanks man! helped a lot, finally someone who said what i wanted to hear = a good explanation!;)

[@bankzxcvB]

hey Mindez from the last step at 10:13 Do you wrong the green circle? i think it should be the 3rd item

[@gbakshi]

Very Helpful and great slides. Really made it clear for me. Thank you.

[@ZachSolcher]

Thank you so much, great video! You really helped me understand dynamic programming. I watched this video through like 4 times :D

[@twistley]

Love how you say "Knapsack" :D

[@sorolopas]

Thanks a lot for this video. Only one questiion. At the last step (to find the solution) you start at the end and you need to find a way to the top( position (0,1)? If you see 1 the you go diagonal and if you see 0 you go up? Thanks!

[@ashihtaka]

when you are on V table of item 2, capacity 4 you put 5 in the V, where it should be 6 because you can have 2 of weight 2 with value 3 and 2*3 = 6

[@VivianLi816]

this was clear and very very helpful. you rock, thanks for sharing!

[@Musathic495]

No, so I'll go into a bit more detail how to do it with a 2-D array. Suppose we have two limiting constrints, M mass and V volume. Our objects that we want to place into our bag have distinct value c, mass m and volume v. We want to select the best set of items to maximize our value without using too much mass or volume. The 3D way is to have, for each of our N objects, a 2-D array of M+1 x V+1 dimension. Then you would apply the same process as demonstrated in this video.

[@jsandroid1665]

great job explaining this man, I really appreciate it! Hopefully you can do some other vids

[@PJ1004]

Great video - thanks for this. Any chance you're doing a video with using multiple items in a knapsack in the near future?

[@MultiPwolf]

Cool video! Here is a python implementation, if it helps anyone. def Knapsack(capacity, values, weights): """ bottom-up dynamic programming solution to knapsack problem """ table = [[0 for columns in xrange(capacity +1)] for rows in xrange(len(values)+1)] for row in xrange(len(values) +1): for column in xrange(capacity +1): if row == 0 or column == 0: #base case, set to zero but as already zeroed continue continue # does item with capacity 'column' fit elif weights[row -1]

[@joshmorley]

awesome explanation, are you able to create a playlist with other videos you did? (i couldnt see one)

[@rohitbhosale460]

finally got this thing.. keep it bro

[@sauragra]

Well explained Sir.. Why don't you consider making more algorithm videos ?

[@charroMX1]

Hey Buddy, Thanks a lot for your explanation. You definitely know how to explain things.

[@MickeyInterviews]

Awesome explanation!!! Any plans of making any other Computer Science Videos?

[@jagajugue]

Hey man, I have a question. In that final case in Keep Table, where you jumped the item and added the next item, if even after add this item remain some space, should I go back for that item that I jumped? In the beginning should I sort my itens by descending weight, or it doesn't matter?