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.
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
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
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.
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)
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 !
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.
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.
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.
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'.
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.
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?
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
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.) ?
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.
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)
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 !
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
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
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?
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!
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/
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
@@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,
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
I think you accidentally put '=' instead of '+' in tmp2(last 3rd line).
at 7:00
CS DOJO common sense dojo
Underrated comment.
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 :)
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.
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?
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
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.
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 :)
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
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'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)
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 !
You are the best Sir.Wish you the best in your life !!
Omg, Thank you for making my life less miserable
Laughed so much. I'm in the exact same position.
@@katalipsi5 Cheers buddy :"D
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
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
using this code as inspiration to solve a really wacky problem right now
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.
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.
Your explanation really hit the core and was helpful.Thanks
One of the best videos I have seen and learned from :) !!!
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
Is there a way to know what items where grabbed?
thanks dojo for explaining in a easy way.
Please fix the typo on your code, great video though!
hi bro please continue posting videos. they are really helpful to the self taught programmers!
Short and simple. Thanks
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.
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.
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'.
Thanks Sir, god bless you
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.
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?
Best Knapsack explanation ever 💯💯
Thank you so much! A really helpful DP refresher for me :D
I finally understand! Thank you!
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.
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.
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
Really good explanation. 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
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.
Best explanation EVER
why 0/1 knapsack needs a 2d array to memoize whereas house robber needs 1d array ? both are similar problems
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?
I love u 3000 for explaining that naive recursive relation...
@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.
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
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 !
Is bottom up method always the efficient method? Pls provide a way to contact about our doubts
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
Why the time per call is a constant time 8:50?
I had the same question!
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
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 "+"?
you my friend... you are the best
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
Hey, what software do you use to create these videos? As in the writing part
Please do show solved problems in the end using both methods.
Ah! I am just 4 years late here.
Please, add more DP videos with examples.
what about bottom up approach
Please make a bottom up approach for your DP videos
love your explanations
your audio is too low??
@CSDojo Why is v[n]=KS(n-1,C-w[n]) in the memoize intermediate result?
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
Very well explained!
Is this not suitable without repetition, right?
Is there a leetcode equivalent of this problem?
you once told about a harvard video collection of algorithm design ,can you tell where can I find it.
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?
No they must be declared. This tutorial just assumes they were declared beforehand since this is not important to the problem.
why cannot we use greedy algorithm
You are the best! Please release some more videos on Algorithms and make a playlist for our entire Algorithms course
Thanks for the wonderful explanation. Please keep making these videos. I am totally dependent on your videos to get a job.
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, helped me a lot
Thank you,this video is concise and goes direct to the point
In tmp2, it should be + instead of = right?
Please make more dp lectures
Which software are they using ?
in base case I guess it should be c
Why used max() function?
Im not speak english, Im not understand all that u said, is it python?
thank you really your vedio is helpful .....Thanks lot from bangladesh
hi, cs dojo. may i request u to iterate through dynamic programming solution to see clearly how it works
oh, I thought only the bottom-up solution can be counted as dynamic programming. hmm...
Good explanation !
How would you return the subset too?
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
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
Why did you take a 5*10 matrix???
because you create a matrix arr[n][c] and n = 5, c=10. So you have 5 row and 10 column
@@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,
Best video i ever seen
I never understand else if (wt[i]>capacity)
ks(wt, val, capacity, i + 1); part ........ thats not even in recursion tree ...................