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.
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] }
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.
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.
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!
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.
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."
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))
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?
@@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
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.
@@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)
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)
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
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 !
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.
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.
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.
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
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.
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!
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'.
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 !
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.
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.
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.
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.
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.) ?
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?
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).
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
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/
This is textbook dynamic programing due to the nature of subproblems being used. However it is important to note that divide and conquer and DP have similar elements.
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.
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.
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)
Quick note: I said "memorization" in this video, but it should be "memoization". Sorry, my mistake.
Please make a bottom up approach for your DP videos
how can we use this for assigning a task to workstations? (in my example workstations are knapsacks)
i had to google memoization to make sure you weren't trolling. jokes on me
this solution is the best for the knapsack problem?
what’s the difference? I have never heard that word before.
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.
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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
I went through a lot of videos on youtube that explains the same problem but this one makes most sense. Thanks CS Dojo :)
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]
}
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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.
When the “naive” solution is the best solution i could come up with 😭
Lol thats the main thing...
If u can come up with the naive recursive solution,then u could easily apply dp to optimise
@@auctal4625 Yeah! DP is basically brute force optimisation and memoization :)
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!
it's not. It will fail the real tests
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
I think you accidentally put '=' instead of '+' in tmp2(last 3rd line).
at 7:00
CS DOJO common sense dojo
Underrated comment.
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).
By the way, the term is "memoize", not "memorize". en.wikipedia.org/wiki/Memoization
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.
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!
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.
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."
He already knows that. Watch the first video of the series. Thank you.
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.
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))
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?
just import lru_cache function from functools and use it as decorator ,nice and clean
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Any way to obtain the list of elements taken?
@@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
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.
Table approach is stupid. Everybody just parroting remembered rules but can't explain how to invent it by yourself and apply for unknown problems
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
@@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)
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)
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
this is basically an iterative approach, right?
@@drj7714 like every bottom up implementation, yes
this doesn’t make sense. where are the weights of each item?
Omg, Thank you for making my life less miserable
Laughed so much. I'm in the exact same position.
@@katalipsi5 Cheers buddy :"D
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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 !
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.
In the video he has mentioned that he is storing some dummy value at 1st index(0th index)
then n==0 || c
One of the best videos I have seen and learned from :) !!!
using this code as inspiration to solve a really wacky problem right now
Your explanation really hit the core and was helpful.Thanks
You are the best Sir.Wish you the best in your life !!
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.
Could you do a video on Big O notation? I've never seen it before, but it looks really useful. Thanks :)
Must watch for anyone interviewing in tech
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.
You are the best! Please release some more videos on Algorithms and make a playlist for our entire Algorithms course
the base case should be if n < 0 or C == 0, otherwise it will miss the 0th index weight
He is starting from n, so the indexes of items is from 1 to n.
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.
hi bro please continue posting videos. they are really helpful to the self taught programmers!
I finally understand! Thank you!
I love u 3000 for explaining that naive recursive relation...
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
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.
We made a video covering this same problem :)
Is there a way to know what items where grabbed?
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.
He puts dummy value as 0th item
thanks dojo for explaining in a easy way.
Short and simple. Thanks
oh, I thought only the bottom-up solution can be counted as dynamic programming. hmm...
Please do show solved problems in the end using both methods.
Ah! I am just 4 years late here.
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!
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Really good explanation. Thank you!
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'.
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 !
you my friend... you are the best
Please fix the typo on your code, great video though!
The ending is rushed a bit. How do you know the table will only take up n*c space? That confused me.
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.
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.
It's filling in an array that is n*C.
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.
Thank you so much! A really helpful DP refresher for me :D
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.
That's actually the greedy algorithm for the Knapsack problem in which you can take fractions of objects as well.
Yeah, for example 6kg-9dollar and 5kg-5dollar and 5kg-5dollar
KP is exactly there to remind you that greedy algorithms won't always work. :D
your solution will be applicable to fractional knapsack problem but not for 0-1 knapsack problem.
In the recursive solution, what if n equals 1 and c equals 1, and the result is 5 which is not supposed.
Thanks Sir, god bless you
Best Knapsack explanation ever 💯💯
thank you really your vedio is helpful .....Thanks lot from bangladesh
@CS Dojo - Great explanation. But even though you use memoization here, the time complexity still remains 2^n isn't it?
no it should be O(nc). The repetition will be caught by the mem table and return directly.
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.) ?
nvm, kept reading comments and found why this would work :P
I never understand else if (wt[i]>capacity)
ks(wt, val, capacity, i + 1); part ........ thats not even in recursion tree ...................
Is bottom up method always the efficient method? Pls provide a way to contact about our doubts
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?
Thanks, you saved my ass.
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.
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?
love your explanations
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 "+"?
At 8:44, can someone explain why the time/call is constant?? Thanks
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).
great man!!
Best explanation EVER
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Thank you for the video, it fucked my brain T_T.
Thanks for the wonderful explanation. Please keep making these videos. I am totally dependent on your videos to get a job.
I feel in over my head lol.
Please, add more DP videos with examples.
Very well explained!
Im not speak english, Im not understand all that u said, is it python?
your audio is too low??
hi, cs dojo. may i request u to iterate through dynamic programming solution to see clearly how it works
in base case I guess it should be c
Wow, thank you for making this video. It is very clear! Well explained >...< Ah, saved the day!
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/
advertisement
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Please make a bottom up approach for your DP videos
Thank you, helped me a lot
Best video i ever seen
Is there a leetcode equivalent of this problem?
Thank you,this video is concise and goes direct to the point
This helps really much!!!
why cannot we use greedy algorithm
Sorry, did i miss something? How do you display maximum value and list of weights included in the result?
he displays only the maximum value, you could use backtracking to find the list of weights
This is Divide and Conquer not dynamic programmming.
This is textbook dynamic programing due to the nature of subproblems being used. However it is important to note that divide and conquer and DP have similar elements.
damn this was easy??? thanks so much!
Is this not suitable without repetition, right?
Yay I finally understood Knapsack! Thanks CS Dojo
Hey, what software do you use to create these videos? As in the writing part
So we add a dummy variable to the array to get the right element. Lol what does this even mean..
Kind sucks that in this example, caching values only saves us 3 calculations out 25 ([0,1], [0,3], and [0,5]) lol
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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.
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.
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)
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Why used max() function?
what about bottom up approach
Why the time per call is a constant time 8:50?
I had the same question!
@CSDojo Why is v[n]=KS(n-1,C-w[n]) in the memoize intermediate result?