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.
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
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
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."
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.
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 !
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)
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!
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?
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.) ?
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).
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.
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 !
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'.
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.
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.
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.
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
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
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)
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
Yes. You need to understand recursion first before you can grasp DP. I cover very basic recursion problems here: ruclips.net/video/aFvY_aZPmqk/видео.html
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/
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.
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 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
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.
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
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 :)
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
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).
I went through a lot of videos on youtube that explains the same problem but this one makes most sense. Thanks CS Dojo :)
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?
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.
I think you accidentally put '=' instead of '+' in tmp2(last 3rd line).
at 7:00
CS DOJO common sense dojo
Underrated comment.
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
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.
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 !
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)
Omg, Thank you for making my life less miserable
Laughed so much. I'm in the exact same position.
@@katalipsi5 Cheers buddy :"D
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)
You are the best Sir.Wish you the best in your life !!
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Your explanation really hit the core and was helpful.Thanks
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 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.
using this code as inspiration to solve a really wacky problem right now
Is there a way to know what items where grabbed?
hi bro please continue posting videos. they are really helpful to the self taught programmers!
Short and simple. Thanks
Thanks Sir, god bless you
thanks dojo for explaining in a easy way.
One of the best videos I have seen and learned from :) !!!
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
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.
Really good explanation. Thank you!
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!
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
thank you really your vedio is helpful .....Thanks lot from bangladesh
In the recursive solution, what if n equals 1 and c equals 1, and the result is 5 which is not supposed.
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?
Please fix the typo on your code, great video though!
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?
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.
I finally understand! Thank you!
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
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).
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.
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 "+"?
Is bottom up method always the efficient method? Pls provide a way to contact about our doubts
Thank you so much! A really helpful DP refresher for me :D
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 !
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 about bottom up approach
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.
Best explanation EVER
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
You are the best! Please release some more videos on Algorithms and make a playlist for our entire Algorithms course
Please, add more DP videos with examples.
@CSDojo Why is v[n]=KS(n-1,C-w[n]) in the memoize intermediate result?
Best Knapsack explanation ever 💯💯
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 my friend... you are the best
Please do show solved problems in the end using both methods.
Ah! I am just 4 years late here.
I never understand else if (wt[i]>capacity)
ks(wt, val, capacity, i + 1); part ........ thats not even in recursion tree ...................
hi, cs dojo. may i request u to iterate through dynamic programming solution to see clearly how it works
Thanks for the wonderful explanation. Please keep making these videos. I am totally dependent on your videos to get a job.
Please make a bottom up approach for your DP videos
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.
love your explanations
I love u 3000 for explaining that naive recursive relation...
oh, I thought only the bottom-up solution can be counted as dynamic programming. hmm...
@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.
Is there a leetcode equivalent of this problem?
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
Please make more dp lectures
Why the time per call is a constant time 8:50?
I had the same question!
Very well explained!
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
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
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?
In tmp2, it should be + instead of = right?
Thank you, helped me a lot
Hey, what software do you use to create these videos? As in the writing part
1:22 why the cost is O(2^n)? i thought it's 2n, since you have 2 options for n elements
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
you once told about a harvard video collection of algorithm design ,can you tell where can I find it.
great man!!
your audio is too low??
Is this not suitable without repetition, right?
why cannot we use greedy algorithm
I find this code hard to understand maybe I should watch more videos of recursion to understand
Yes. You need to understand recursion first before you can grasp DP. I cover very basic recursion problems here: ruclips.net/video/aFvY_aZPmqk/видео.html
I feel in over my head lol.
Wow, thank you for making this video. It is very clear! Well explained >...< Ah, saved the day!
Good explanation !
Is it not a np complete problem?
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
Im not speak english, Im not understand all that u said, is it python?
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
in base case I guess it should be c
Can anyone explain why the total number of total solutions at the start is 2^n?
pjately078 because each problem has 2 solutions - yes and no
It is a binary tree that is horizontal. So it's like traversing all nodes in a binary tree.
How would you return the subset too?