0-1 Knapsack Problem (Dynamic Programming)

[@CSDojo]

Quick note: I said "memorization" in this video, but it should be "memoization". Sorry, my mistake.

[@coolchetang]

Please make a bottom up approach for your DP videos

[@javadkhalilarjmandi3906]

how can we use this for assigning a task to workstations? (in my example workstations are knapsacks)

[@Naton]

i had to google memoization to make sure you weren't trolling. jokes on me

[@kacperomg7935]

this solution is the best for the knapsack problem?

[@saif0316]

what’s the difference? I have never heard that word before.

[@danieljacksoncavalcantecos3751]

On 7:03, tmp2 should receive with v[n] + KS(n-1, C-w[n]), instead of v[n] = KS(n-1, C-w[n]) :v

[@nir.j]

I like how you concentrate more on the recursive DP implementation when most other tutorials I came across were Bottom-up. Thank you for the great videos, looking forward to more of them.

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@jonathanguillotte-blouin4327]

By the way, the term is "memoize", not "memorize". en.wikipedia.org/wiki/Memoization

[@legume-dc2zx]

From an understanding point of view, "memorize" makes a lot more sense intuitively. So "memorize" would be the better explanation to use. Anyone can pick up a textbook (or find a wikipedia article) and find fancy words. I'm watching the video to get an intuitive understanding.

[@jonathanguillotte-blouin4327]

Kelvin Shi sorry it rubbed you the wrong way. The video is very good, and yes "memorize" comes to mind intuitively, but that doesn't make it more right to say. Maybe it's not important to you, but if others are interested and want to look further into the subject, I'm sure they won't mind knowing the correct term. Have a nice day!

[@MsClrs]

Kelvin Shi the video is brilliant. No doubts. Since we have specific technical terms for certain aspects, its better to teach em that way especially if someone is just learning, its better to learn it right. No need to dumb it down. After all, it is dynamic programming, its not itsy bitsy spider. So know your audience.

[@balasuar]

No, it doesn't. "Caching" would make a lot more sense. Computers don't have the ability to "memorize" information. But storing off pre-computed values--aka caching, is completely intuitive. The correct term is "memoize" not "memorize."

[@almeida.cavalcante]

He already knows that. Watch the first video of the series. Thank you.

[@jameswu3513]

When the “naive” solution is the best solution i could come up with 😭

[@auctal4625]

Lol thats the main thing... If u can come up with the naive recursive solution,then u could easily apply dp to optimise

[@sanskarsharma9494]

@@auctal4625 Yeah! DP is basically brute force optimisation and memoization :)

[@jamesrippel8032]

Great video, have been looking for a clear and concise answer to this problem. I struggled a bit adapting the syntax to Javascript so here it is as implemented in the Knapsack Light challenge on codefights and codewars if anyone's interested: function knapsackLight(value1, weight1, value2, weight2, maxW) { let values = [0, value1, value2]; let weights = [0, weight1, weight2]; let resArr = []; function consider(n, C){ let res; if(n === 0 || C === 0){ res = 0; } else if(weights[n]>C){ res = consider(n-1, C); } else{ let tmp1 = consider(n-1, C) let tmp2 = values[n] + consider(n-1, C - weights[n]) res = Math.max(tmp1, tmp2) } return res; } var finalRes = consider(2, maxW) return finalRes } And with dynamic programming: function knapsackLight(value1, weight1, value2, weight2, maxW) { let values = [0, value1, value2]; let weights = [0, weight1, weight2]; function fillArray(n) { var arr = Array.apply(null, Array(n)); return arr.map(() => undefined); } let resArr = fillArray(3); for(i=0;iC){ res = consider(n-1, C); } else{ let tmp1 = consider(n-1, C) let tmp2 = values[n] + consider(n-1, C - weights[n]) res = Math.max(tmp1, tmp2) } resArr[n][C] = res; return res; } var finalRes = consider(2, maxW) return resArr[resArr.length - 1][resArr[2].length-1] }

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@sangramreddy5549]

Neat and Great. All other videos are drawing tables and going crazy. It would have been nice if you showed an example pair n,C where we don't recalculate because we already stored the outcome for the pair.

[@mirceanicolaescu9804]

The bottom up approach does not need to store all the n-1 previous values. Only the previous two. This would get the space complexity down to O(1).

[@naeem_akhtar]

I think you accidentally put '=' instead of '+' in tmp2(last 3rd line). at 7:00

[@anshuprince8800]

CS DOJO common sense dojo

[@amey7064]

Underrated comment.

[@marksy971]

Base case should be: if(n < 0 || c < 0). Image if we have capacity of 10 and a weight-value pairs of (5 wt, 10 val). When we recurse result will become 10 and then 10+0. To fix this we should return if the capacity become negative or it the position in the array becomes negative.

[@akashmc]

In the video he has mentioned that he is storing some dummy value at 1st index(0th index)

[@abhayagarwal227]

then n==0 || c

[@threedwb]

It was quick and Really good, best one for Knapsack ... Actually it will be really good if you can do the bottom-top one too. Thanks!

[@JohnDoe-fv5cu]

it's not. It will fail the real tests

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@dulat1]

If anyone's interested here is a bottom up implementation in C++. It works almost like a recursive one except instead of function values and memo we need a table. Recursive approach might lead to stack overflow that's why bottom up is better I guess. #include using namespace std; int main() { int n; // number of elements int c; // initial capacity cin>>n>>c; vector v(n+1); // 0th index is just a dummy value for convenience for (int i=1; i>v[i]; int table[n+1][c+1]; for (int i=0; itmp2) table[i][j]=tmp1; else table[i][j]=tmp2; } } } cout

[@drj7714]

this is basically an iterative approach, right?

[@hil449]

@@drj7714 like every bottom up implementation, yes

[@Kenttheclark]

this doesn’t make sense. where are the weights of each item?

[@BobbyBattista]

Thanks, this was really helpful! Here it is in python with memoization and not requiring a dummy entry in the arrays: cache=dict() def knapsack(n, remaining): if (n, remaining) in cache.keys(): return cache[(n, remaining)] #base case if n < 0 or remaining == 0: # If on items left, or we already hit our max weight, we're done with this path return 0 if wt[n] > remaining: # if the current weight is more than remaining capacity, skip it, but keep trying other weights return knapsack(n-1, remaining) take = val[n] + knapsack(n-1, remaining-wt[n]) skip = knapsack(n-1, remaining) cache[(n, remaining)] = max(take,skip) return cache[(n, remaining)] print(knapsack(len(vals)-1, W))

[@AaronBrand]

I'm learning. Thanks for this; I've copied and I'm adding to my studies! edit: for some reason, val and vals come back as undefined. are they part of a library that I need to import?

[@abdelrhmanahmed1378]

just import lru_cache function from functools and use it as decorator ,nice and clean

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@tanvirkaisar7245]

Any way to obtain the list of elements taken?

[@BobbyBattista]

@@tanvirkaisar7245 Off the top of my head I'm not sure, but I remember writing a solution for the "minimum amount of coins" problem that included which coins were taken. This was several years and several laptops ago though - if I find something, I'll share here

[@mazjaleel]

I've never seen someone using memoization for solving 0-1 knapsack .. it's a lot simpler for my recursive mind to follow, rather than the table approach usually presented in other sources.

[@dmitrysamoylenko6775]

Table approach is stupid. Everybody just parroting remembered rules but can't explain how to invent it by yourself and apply for unknown problems

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@ucanhly1166]

@@jaideepsingh7955 we can know how many dimension of array for dp by tracking what value are changed of each state (recursive state) in this case (n = index of bag we chose , C = capacity)

[@shashankrajholavanalli2868]

I went through a lot of videos on youtube that explains the same problem but this one makes most sense. Thanks CS Dojo :)

[@SimoneGirardi]

Try to let C = 2^n 😁. It’s important to say that it isn’t a polynomial solution (this problem shouldn’t have it). You can only find a solution near to the optimal solution in polytime (in size of “n” and 1/epsilon, with epsilon > 0)

[@pg9645]

You are the best Sir.Wish you the best in your life !!

[@RameshVeeramani]

Your explanation really hit the core and was helpful.Thanks

[@penguinmonk7661]

Thank you, very clear and a great refresher, saved me waiting for a book that I borrowed to someone, and helped me finish me work.

[@nachoman400]

Is there a way to know what items where grabbed?

[@skepticbubble3166]

Omg, Thank you for making my life less miserable

[@katalipsi5]

Laughed so much. I'm in the exact same position.

[@skepticbubble3166]

@@katalipsi5 Cheers buddy :"D

[@emmabarron6578]

Could you do a video on Big O notation? I've never seen it before, but it looks really useful. Thanks :)

[@vanesslifeygo]

using this code as inspiration to solve a really wacky problem right now

[@zzzz26526]

I used to be scared of recursion but I know realize how powerful it can be when you apply dp to it, not to mention how short the solution is.

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@rajivr1944]

Dear YK Sugi, Explanation of recursive problem solutions is a bit tricky. I must commend you on the fine job you do in explaining your approach and solutions. Thanks !

[@heizerov]

It appears there is a typo starting from 6:59, the line that assigns to tmp2 should read: temp2 = v[n] *+* ks(...). You put an equals sign instead of the plus sign.

[@cindygao9921]

The ending is rushed a bit. How do you know the table will only take up n*c space? That confused me.

[@eddiemay1999]

That math is not correct. The solution was 2^n recursive, with n = 5, that's 32. And he is saying with dynamic programming the solution would be n*c which is 5x10 which is 50. The solution just got worse? 10 is the total weight you can carry, it makes no sense to multiply by that. The real answer should be something less than 2^n since you get to short cut anytime you reach the same element with the same remaining capacity but I don't know exactly what it would be.

[@code_explorations]

Eddie Mayfield Interesting! 32 vs 50. I think the 32 is a time complexity (first solution) but the 50 is a space complexity (second solution). So they may not be comparable. But I think the video did compare them, so I'm not sure. It seems obvious that the second solution is better because some calculations (and stack frames) will be avoided. Maybe we have to use larger input data to see the payoff. So, yeah: good video, but rushed at the end.

[@code_explorations]

It's filling in an array that is n*C.

[@ahmetozdemir2207]

Actually, you are thinking it in a wrong way. First of all, for this particular case, maybe 2^n time complexity is better but when it gets bigger which means when n is bigger than 6, it will be the worse. For example, consider that you have 10 items. Then time complexity will be 2^10 which is 1024. However, 10*10=100. Therefore, you actually can check this situation in your code that is to say, maybe you can compare n*C and 2^n and if one of them is less than another, you can call corresponding function which is still not exactly necessary in my opinion.

[@wrich2000]

my first thought was take each ratio, sort, then take until full. A lot simpler, and pretty much what a human would do naturally. But I realized there are some edge cases that it wouldn't work, guess that's why humans are bad computers.

[@tanavyadimri2421]

That's actually the greedy algorithm for the Knapsack problem in which you can take fractions of objects as well.

[@namlehai2737]

Yeah, for example 6kg-9dollar and 5kg-5dollar and 5kg-5dollar

[@Papayalexius]

KP is exactly there to remind you that greedy algorithms won't always work. :D

[@prashantpatel1]

your solution will be applicable to fractional knapsack problem but not for 0-1 knapsack problem.

[@utkarsharaikar816]

Hey YK, it'd be great if you could explain the solution to the problem 'Minimum number of characters to be deleted to make the given string a palindrome'.

[@aok1425]

If 7:00 is in Python, the base case line should be n < 0 instead of n == 0, bc we do want to look at the 0th item.

[@smiejacysiekanal]

He puts dummy value as 0th item

[@dnavas7719]

Best Knapsack explanation ever 💯💯

[@uripre]

Not sure I understand - in the worst case, for example when weights are unique powers of two - each combination has a completely different C. So that would be basically still 2^n as the cache would never hit twice. Am I wrong?

[@beyondmeaning]

Must watch for anyone interviewing in tech

[@ankitsharma8221]

The time complexity for the memoization version is actually O(nc) and yes that breaks apart when comparing to 2^n as its 32 vs 50, but that's the beauty of programming. You need to know when to use which variant. www.geeksforgeeks.org/knapsack-problem/

[@anonymousbeing922]

advertisement

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@mrnobodyy96]

Please fix the typo on your code, great video though!

[@gopalrv9703]

the base case should be if n < 0 or C == 0, otherwise it will miss the 0th index weight

[@coding953]

He is starting from n, so the indexes of items is from 1 to n.

[@brockobama257]

Okay but what if we tweak the problem so each node has one of 3 colors and we need to maximize the set of nodes with 1 blue 1 red and 1 green node?

[@mingjing7995]

Hey! Thanks for you video inspiring me a lot as a programming beginner. But may I ask that in the KS function you showed between 5:00 ~ 6:00 around, can I remove the second “else if w[n] > c”, and make the first condition if n ==0 or C

[@ShrubScotland]

two years ago...but... if C is zero, you are essentially saying "it's impossible to fit any more items in this bag, return 0" if C is non-zero, but less than the weight of the selected item, you are saying "this item will not fit in this bag, but maybe the next one will, try the next one" So they are two different things and can't be combined. You could omit the C == 0, but that would be inefficient because you would be continuing to check against all the items even when though it's impossible to fit any more items in the bag.

[@geekyprogrammer4831]

hi bro please continue posting videos. they are really helpful to the self taught programmers!

[@AfroMuggleKing]

Can you show how bottom up is different from top down approach? I feel Bottom approach is easier to read and to figure out time complexity.

[@omartahboub2900]

One of the best videos I have seen and learned from :) !!!

[@FredoCorleone]

I want to point out that the "if-else" is not necessery, as you may notice you are repeating KS(n-1, C) in both the "if" and the "else", you could have just used a single "if" for tmp2 calculation. You didn't show where are those repetition to memoize.

[@auctal4625]

I love u 3000 for explaining that naive recursive relation...

[@piyushsharma1638]

thanks dojo for explaining in a easy way.

[@peterhorst2710]

what if we had didn't only have the binary option yes and no, but also how *many* we want to take ? Like options are, take 0,1 or 2, and then go on with the next item. How to realize that ? Can you compare the different path total values and take the max ? i didn't find any other good video to take on this problem. Nonetheless, great video !

[@TheCndra]

In the recursive solution, what if n equals 1 and c equals 1, and the result is 5 which is not supposed.

[@VIPtiny]

@CSDojo Why is v[n]=KS(n-1,C-w[n]) in the memoize intermediate result?

[@YelloDuck-oo5cn]

I can see that at line 10 in the dynamic solution, tmp2 is = v[n] = KS(n-1, C - w[n]). Is the second "=" supposed to be a "+"?

[@svdfxd]

@CS Dojo - Great explanation. But even though you use memoization here, the time complexity still remains 2^n isn't it?

[@liwaiyip1769]

no it should be O(nc). The repetition will be caught by the mem table and return directly.

[@Lellba47]

Wouldn't it be much better to calculate for each set of weight-value a *value per kilogram* (value/weight), sort the list and then take the elements in order, until the bag is full (skipping elements which make the weight sum exceed the max.) ?

[@Lellba47]

nvm, kept reading comments and found why this would work :P

[@coolchetang]

Please make a bottom up approach for your DP videos

[@jeehacks5129]

Is bottom up method always the efficient method? Pls provide a way to contact about our doubts

[@nandkumarpawar7]

Please do show solved problems in the end using both methods. Ah! I am just 4 years late here.

[@BackToBackSWE]

We made a video covering this same problem :)

[@sovanmondal2621]

Please, add more DP videos with examples.

[@kemal4282]

in base case I guess it should be c

[@tonytoeknee3192]

At 8:44, can someone explain why the time/call is constant?? Thanks

[@dnavas7719]

Because if you look at every operation the function does, they're all constant. Edit: all statements inside the function take constant time, therefore calling the function takes O(1).

[@faramarzkhosravi]

I could not get the dynamic programming-based version to run! Perhaps there is a bug in the memoization (which worked well for problems in your other videos). Keeping a table with C columns makes not much sense, because C or weights can be real values that could not be used for indexing.

[@faramarzkhosravi]

This memoization does not help because if you write down the whole binary tree, you see that either the nodes have different pairs of (n, c) or they represent completely different scenarios. For example, (n, c) = (1, 8) represents both {0,1,0,0,0} (only second item is selected) and {0,0,0,1,0} (only forth item is selected), which are completely different solutions. Memoization only helps when two sub-solutions are exactly the same and you do not want to re-calculate the exact same thing.

[@faramarzkhosravi]

I tried to implement the memoization using dictionary, with each key being a tuple (n, c), and it worked. Here is my code: def helper(weights, values, results, current, capacity): key = (current, capacity) if key in results: return results[key] result = 0 if current < 0: result = 0 elif weights[current] > capacity: result = helper(weights, values, results, current-1, capacity) else: r1 = helper(weights, values, results, current-1, capacity) r2 = values[current] + helper(weights, values, results, current-1, capacity - weights[current]) result = max(r1, r2) results[key] = result return result def knapsack(weights, values, capacity): last_index = len(w) - 1 results = {} return helper(weights, values, results, last_index, capacity) w = [1, 2, 4, 2, 5] v = [5, 3, 5, 3, 2] c = 10 total_value = knapsack(w, v, c) print(total_value)

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@conjoguam]

Sorry, did i miss something? How do you display maximum value and list of weights included in the result?

[@diamantis5099]

he displays only the maximum value, you could use backtracking to find the list of weights

Really good explanation. Thank you!

[@emilyli6325]

wonderful video! I've watched serveral other videos explainning DP but still confused. After watching your video, i finaly understand, you made dp problem easy to understand and quite to the point. Thank you for the great work!

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@dmitrysamoylenko6775]

Best explanation EVER

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@XnDxNdXnD]

Short and simple. Thanks

[@la-hp4uc]

hi, cs dojo. may i request u to iterate through dynamic programming solution to see clearly how it works

[@amarnathkarthi9172]

Hey, what software do you use to create these videos? As in the writing part

[@abb8493]

you once told about a harvard video collection of algorithm design ,can you tell where can I find it.

[@jinyang4796]

Thank you so much! A really helpful DP refresher for me :D

[@asahikitase5398]

oh, I thought only the bottom-up solution can be counted as dynamic programming. hmm...

[@ReactoPhile]

You are the best! Please release some more videos on Algorithms and make a playlist for our entire Algorithms course

[@MrVarsityphysics]

Kind sucks that in this example, caching values only saves us 3 calculations out 25 ([0,1], [0,3], and [0,5]) lol

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@lellobidello2301]

1:22 why the cost is O(2^n)? i thought it's 2n, since you have 2 options for n elements

[@verushannaidoo9450]

At every stage you either take a value or don't. So picture it like there's at most 5 items to choose from, and for each of these items, we could either put them in the sack or don't. So using place holders, the possibilities for each item would be 2 2 2 2 2, which is 2 ^ 5

[@sonofgod00]

Thanks Sir, god bless you

[@remixisthis]

I would also HIGHLY recommend the Dynamic Programming series here for a more in-depth look at DP: kzbin.info/www/bejne/pXPXZmaPl7dsgc0

[@useruser12341]

I find this code hard to understand maybe I should watch more videos of recursion to understand

[@bparanj]

Yes. You need to understand recursion first before you can grasp DP. I cover very basic recursion problems here: kzbin.info/www/bejne/l3fZipKXj7Wgp80

[@PoojaMehta271]

Is there a leetcode equivalent of this problem?

[@niharikasinha3390]

In tmp2, it should be + instead of = right?

[@mml1677]

you my friend... you are the best

[@sabbirsaadat344]

hello, new here in python. So let me get this straight: you CAN use an undeclared variable (in this case, the arrays w & v) within a function if they are presumed to be global variable?

[@AndrewSmith-pn2qc]

No they must be declared. This tutorial just assumes they were declared beforehand since this is not important to the problem.

[@davidwu1907]

Why the time per call is a constant time 8:50?

[@toekneemusic9732]

I had the same question!

[@ashrafulfuad2967]

thank you really your vedio is helpful .....Thanks lot from bangladesh

[@peisu9453]

Is this not suitable without repetition, right?

[@shubhamkumar-pp1zf]

your audio is too low??

[@Animalcrossing35]

I finally understand! Thank you!

[@devanshsharma5704]

love your explanations

[@keshavmaheshwari521]

why cannot we use greedy algorithm

[@HareKrishnaWavecity]

what about bottom up approach

[@ashishtrivedi6426]

I never understand else if (wt[i]>capacity) ks(wt, val, capacity, i + 1); part ........ thats not even in recursion tree ...................

[@tonmoyrakshit1717]

The base case should be n

[@noahabrey7546]

well that is safe too, but the code shouldn't allow n or C to be set to values lower than 0. so I don't think you can say it "should" be those conditions

[@tonmoyrakshit1717]

@@noahabrey7546 Design for failure! Do we want the function to work on negative values of n or C?

[@noahabrey7546]

@@tonmoyrakshit1717 well you're right, i think its good practice to have it safe like that, but I think for the sake of demonstrating the algorithm it is fine to have it n==0 || C==0, because it helps viewers recognize that we are going to count down and eventually hit zero, without the possibility of going below. The function itself won't allow these values to go below zero. The only time the values could be below zero would be if you passed values initially to the function incorrectly.

[@isaacking4555]

For some reason this video didn't click for me so I went to Abdul Bari as he clearly explained the formula and approach step by step. Maybe Im just a bit slower but hope this helps people who just didn't get it here :/ Don't feel bad if you didn't get it, you're not alone at least aha

[@jaideepsingh7955]

why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems

[@Deepakkumar-dv7up]

Thanks for the wonderful explanation. Please keep making these videos. I am totally dependent on your videos to get a job.

[@BeetBlueyou]

Im not speak english, Im not understand all that u said, is it python?

[@DanyloYoutubylo]

So we add a dummy variable to the array to get the right element. Lol what does this even mean..

[@ayushigupta7156]

Which software are they using ?

[@quantlfc]

Why did you take a 5*10 matrix???

[@lethanhtu125]

because you create a matrix arr[n][c] and n = 5, c=10. So you have 5 row and 10 column

[@ctchang0824]

@@lethanhtu125 could u please explain why the possible pairs number is nxC ? In the case in video, it only could have result for (5,8) and Not possible for (5,9) cause the 5th item weight is 2. If so, how could the number of pairs is nxC in total ? Thanks,

[@Kuchbhi24211]

Why used max() function?

[@surajchavda]

Very well explained!

[@josesoto3594]

at first l thought it was super complex and you didn't explain it as good as you usually do in your other videos, then l realized l was being dumb. If you pause the video and read the code at 7:00 it's perfectly understandable

[@hellgheast97]

Thank you,this video is concise and goes direct to the point

[@arturolara1770]

How would you return the subset too?