I am a bit confused. Shouldn't C(2) be equal to C(1) + C(1)? and for C(n) it should be max[C(i) + C(n-i)] ? since wouldn't we want the most profitable way to cut BOTH [0..i] and [i+1...n] sections of the rod? Why are we only taking the optimal way to cut one section plus the normal price of cutting the other? Why not the optimal way to cut that also? Meaning, Shouldn't we do C(K) instead of V(K)? Someone plz explain why we are only getting the C() value for only one section of the division and the V() value for the other when I think it should be C() value for both
I was just about to say this. This is bottom up because we are starting from the most primitive of values C(1) and working our way up to the top most value C(j). Most memoization algorithms work from bottom up like the rod cutting programming.
This is not bottom up, its actually top down approach because the function will be recursive, will start from N continuous call till 0, then from 0 it will keep on solving to top, understand the concept. Anyway, this process is called memoization and its mean top down. This can also be solved using tabulation, no recursive call on this case, the loop will simply start from 0 continue to N, that is bottom up. Now u get it?
There were 45 people who have zero CS knowledge and don't know the difference between top down and bottom up approach. Unfortunately, these are the same people who get hired by FAANG. This is TOP DOWN!
15.8 you mentioned its top down approach, I think this is bottom up approach, isn't it? we are considering from the first piece and moving top to get bigger and bigger piece by combining smaller pieces.
Oh right, it depends on if I use the recursive approach with memoization I will have to go Top Down and solve the base case -> Store and Use it. Makes sense. O (n^2) for n length + n recursive calls. The Later case with the Bottom-up approach, we use 2 for loops. O (n^2)
In memoization, there is the advantage of solving only the necessary of the subproblems but the overhead of increased space due to the recursive call stack. In tabulation, or bottom up approach, where all the smaller subproblems are solved first and thus the solution to the required problem found, there is the overhead of solving unnecessary subproblems but the advantage of reduced space complexity.
I was trying to understand this problem and couldn't wrap my head around the mechanism. Now, finally after watching this video finally understood the mechanism used 🥲. Thank you very much 🥲❤
Why are you doing V_3+C(5) than V_5 + C(3) and not just C(3) + C(5)? It seems to me that in some cases C(3) + C(5) can be bigger than max(V_3+C(5) ,V_5 + C(3) ) and your solution may not be optimal, am I wrong?
Very good demonstration. However to clearly communicate the reuse of value for dynamic programming the whole table would be useful. The demonstration shows the repeated calculation at each step rather than showing the lookup of the table from the previous steps.
this is only reverse engineering of the root problem. The business actually start from scratch like their shampoo product can be distribute in 10ml, 20ml, 250ml, 500ml, 1ltr qty now the possibility of buying
Thats pretty simle to understand if you will think about it carefully. What is 'i'? Its the lenght of a rod. What is 'k'? 'k' is the size of a rod we can cut off. What does Vk + C(i-k) means? It means we cut a subrod of size 'k' (which price is Vk) and we left with a reminder of a rod with size i-k. Now what is the price of a reminder of size i-k - we already calculated it in array of prices C, it is C(i-k) and we come to the recurrent formula
I don't think so...let's say your statement is indeed true, then why did they bother to give us a price array?.. You can't build a revenue array if you don't use the input price array...You can't either demonstrate the optimal sub structure proof.. that ad-hoc thing will return the same thing unless you change the k..Good luck ;)
You are right. That was wrong, the price was not used. Later on, I found in order to make max{Ck+C(i-k)} work, I've to pre-load C(1)=1, C(5)=1, C(25)=1....before the iteration starts, so the algo knows when to use one coin instead of many.
No... what they had on the screen was right, if you took C(k), you would be looking at the optimal values not the price for the specific value of a rod of x length. Vk is looking at the other side of this addition which is the static original values. The optimal substructure part is the C(i-k). So what you're doing is adding one part optimal substructure and one part original value to determine the NEXT single best cut to make, so original values, Vk, still come into play. Subtle point, but this had a few too many up votes and the author is not keeping up.
in this case wouldn't it be much simpler to take a ratio of cost/length for each sublength and apply the highest ratio to the total length we want to cut until the remaining piece is smaller than the highest ratio piece and then cutting the next highest ratio length that we can... e.g. length 6 has the highest ratio so we prefer to cut 6-lengths from the rod until we have less than length 6 remaining then we cut the next highest ratio length until we have cut all??
This is the greedy algorithm for this problem. It does not guarantee an optimal solution, however. And you want more money for your rod don't you? You worked hard for that rod. You better cut that rod the best possible way you can.
@@joshuawest3247 Hi. I often come across this statement that a greedy algorithm does not "guarantee" an optimal solution. Could you please explain why this is so? An algorithm is supposed to work out is it not? If a greedy algorithm does not produce an an optimal solution, that would make it in*correct* and not merely in*efficient*, correct? Also, could you give an instance of the rod - cutting problem where the greedy algorithm does not work? Hope for a reply, thanks.
While this explanation is nice, it does not support multiple cuts (ex: 1,1,2 for 4). Although not applicable in this example, a lot of the time, the optimal price is based off of more than just 1 cut.
![[Algorithms] Dynamic programming for solving the rod cutting problem](http://i.ytimg.com/vi/L9Y1pqtptPE/mqdefault.jpg)
I have been looking for a good video for this problem! This one explains it better than the rest.
Thank you so much for putting this together. This helped me a lot with my algorithms class.
Frank Navarro Thanks for watching! Glad that it helped.
this is by far the best explanation out there for the "rot cutting problem"
One of the best tutorial for rod-cutting problem!!
Man you made this a cakewalk. Thanks Bro. :-)
I wish I had come across this video earlier and not after 5 hours of breaking my head on this problem. thanks mate
Thank you very much! The first time I saw this problem in CLRS it got the shit out of me. You make it seem so easy! Continue your good work.
I was puzzled with the Rod Cut Algorithm in my class. Thank you so much for putting it together in such an easy way. It helped me a lot. :-)
Great video. Helped me understand easier than the pseudo code in my textbook.
the best algorithm vid i ever watched
This video is very good enough to understand well in rod cutting problem
thank you for teaching, you too have a great day, salute!
you are the only one who rescued my life from this conception dynamic programming. this concept is good but devil :( :)
This video is my life saviour. EASY AND PERFECT explanation!
Thank you so much. You have explain it way better then my instructor.. XD
Your videos are really helpful! Thank you very much!
You gotta stay calm and composed when learning DP first. Its really messy.
Thanks for the video. Great work
nice advice thanks man
Clearly explained! Thank you so much for making this video!
You are awesome. I get it now. Thank you so much sir.Here at the Matrix, we love you!!!
Very well explained. Thank you so much!
It finally clicked, thankyou for the amazing video
Thank you for the video!
Thank You So Much!!! very well explained .. you really make it seem so easy .. now i am confident .. Keep up the good work ..
I am a bit confused. Shouldn't C(2) be equal to C(1) + C(1)? and for C(n) it should be max[C(i) + C(n-i)] ? since wouldn't we want the most profitable way to cut BOTH [0..i] and [i+1...n] sections of the rod? Why are we only taking the optimal way to cut one section plus the normal price of cutting the other? Why not the optimal way to cut that also? Meaning, Shouldn't we do C(K) instead of V(K)? Someone plz explain why we are only getting the C() value for only one section of the division and the V() value for the other when I think it should be C() value for both
I came looking for an answer to this caus I agree with you, but your comment is 2 years old so i guess i'll never find out
Great work and explaination Thank you
The approach used here is bottom up not top down ....
My professor is not specifying if it has to be top down or bottom up on my test so I will choose this way.
Why bottom up
I was just about to say this. This is bottom up because we are starting from the most primitive of values C(1) and working our way up to the top most value C(j). Most memoization algorithms work from bottom up like the rod cutting programming.
This is not bottom up, its actually top down approach because the function will be recursive, will start from N continuous call till 0, then from 0 it will keep on solving to top, understand the concept.
Anyway, this process is called memoization and its mean top down.
This can also be solved using tabulation, no recursive call on this case, the loop will simply start from 0 continue to N, that is bottom up.
Now u get it?
There were 45 people who have zero CS knowledge and don't know the difference between top down and bottom up approach. Unfortunately, these are the same people who get hired by FAANG. This is TOP DOWN!
Thank you soooo much sir. I have never been able to understand this. Please do on backtracking this way. Thanks again..
I'm looking for best one. so, here it is.
thank you so much sir, it help full to my exam
15.8 you mentioned its top down approach, I think this is bottom up approach, isn't it?
we are considering from the first piece and moving top to get bigger and bigger piece by combining smaller pieces.
Oh right, it depends on if I use the recursive approach with memoization I will have to go Top Down and solve the base case -> Store and Use it. Makes sense. O (n^2) for n length + n recursive calls.
The Later case with the Bottom-up approach, we use 2 for loops. O (n^2)
Original Problem was only using pure recursion and not memoization takes O(2^n) exponential time.
DP rocks!
In memoization, there is the advantage of solving only the necessary of the subproblems but the overhead of increased space due to the recursive call stack. In tabulation, or bottom up approach, where all the smaller subproblems are solved first and thus the solution to the required problem found, there is the overhead of solving unnecessary subproblems but the advantage of reduced space complexity.
lots of love to you 😀
Good explanation!
Great Video, great explanation... Thanks
Sir karim is just awesome.upload more videos.
thanks man superb jazallah
GREAT JOB!!
Nice explanation
thanks! perfect explanation.
awesome video tutorial. i like it very much.
thank u.
Great video !
that was really good tnx, Could you pls put presentation file for us too,that would be great
Yeah my professors' explaination was utter shite, thanks for making me understand!
thanks, very methodical.
I got it.Thank you so much.
so so clear! tks!!
you are so good!
It is very useful thank you so much
thank you so much man
you are great
Much love and God bless
Are you still alive? I think you were neutralized by the Indian military in Kashmir :/
I was trying to understand this problem and couldn't wrap my head around the mechanism. Now, finally after watching this video finally understood the mechanism used 🥲. Thank you very much 🥲❤
I liked that first 5 mins - killed the complexity for me. Thanks.
Good Tutorial !
its an usefull video..thanks
helpful, thank you
Thank you !
Thanks a lot
Awesomee!!!! Like really awesome
Why does this work? When you take a Vk and to it V(i-k) wouldn't V(i-k) already have counted Vk using a different combination?
Thanks a lot!
Why are you doing V_3+C(5) than V_5 + C(3) and not just C(3) + C(5)? It seems to me that in some cases C(3) + C(5) can be bigger than max(V_3+C(5) ,V_5 + C(3) ) and your solution may not be optimal, am I wrong?
Very good demonstration. However to clearly communicate the reuse of value for dynamic programming the whole table would be useful. The demonstration shows the repeated calculation at each step rather than showing the lookup of the table from the previous steps.
exactly
i have a question when finding c8 why when we cut it 4 by 4 its 19 isnt a length 4 worth according to the dp array 10 then it would be 20 right?
very nice
this is only reverse engineering of the root problem. The business actually start from scratch like their shampoo product can be distribute in 10ml, 20ml, 250ml, 500ml, 1ltr qty now the possibility of buying
Thanks sir :)
Dear CSBreakdown, How did you derive the recurrence relation?(i.e C(i) = Max{V of k + C(i-k)} . This is not obvious or intuitive to me.
Thats pretty simle to understand if you will think about it carefully. What is 'i'? Its the lenght of a rod. What is 'k'? 'k' is the size of a rod we can cut off. What does Vk + C(i-k) means? It means we cut a subrod of size 'k' (which price is Vk) and we left with a reminder of a rod with size i-k. Now what is the price of a reminder of size i-k - we already calculated it in array of prices C, it is C(i-k) and we come to the recurrent formula
thank you.
Shouldn't it be max{Ck+C(i-k)} ?
Yes, I think it should be max{Ck+C(i-k)}.
I don't think so...let's say your statement is indeed true, then why did they bother to give us a price array?.. You can't build a revenue array if you don't use the input price array...You can't either demonstrate the optimal sub structure proof.. that ad-hoc thing will return the same thing unless you change the k..Good luck ;)
You are right. That was wrong, the price was not used. Later on, I found in order to make max{Ck+C(i-k)} work, I've to pre-load C(1)=1, C(5)=1, C(25)=1....before the iteration starts, so the algo knows when to use one coin instead of many.
C(k) and V(k) can represent the same thing. It's not incorrect but to say C(k) could clear up confusion about where that value comes from.
No... what they had on the screen was right, if you took C(k), you would be looking at the optimal values not the price for the specific value of a rod of x length. Vk is looking at the other side of this addition which is the static original values. The optimal substructure part is the C(i-k). So what you're doing is adding one part optimal substructure and one part original value to determine the NEXT single best cut to make, so original values, Vk, still come into play. Subtle point, but this had a few too many up votes and the author is not keeping up.
Thnx buddy .....
in this case wouldn't it be much simpler to take a ratio of cost/length for each sublength and apply the highest ratio to the total length we want to cut until the remaining piece is smaller than the highest ratio piece and then cutting the next highest ratio length that we can... e.g. length 6 has the highest ratio so we prefer to cut 6-lengths from the rod until we have less than length 6 remaining then we cut the next highest ratio length until we have cut all??
This is the greedy algorithm for this problem. It does not guarantee an optimal solution, however. And you want more money for your rod don't you? You worked hard for that rod. You better cut that rod the best possible way you can.
@@joshuawest3247 Hi. I often come across this statement that a greedy algorithm does not "guarantee" an optimal solution. Could you please explain why this is so? An algorithm is supposed to work out is it not? If a greedy algorithm does not produce an an optimal solution, that would make it in*correct* and not merely in*efficient*, correct? Also, could you give an instance of the rod - cutting problem where the greedy algorithm does not work?
Hope for a reply, thanks.
Is it OK to do C(i) = { max{ C(k) + C(i-k) }, V(i) } where 1
does this work?
In the formula what the hell is 'k'?
Great!
thanks
Thank you so much (Y)
I think max value of k=floor(i/2) should be enough. K do not required to go all the way to i.
I agree. Also, c[] should be initialized with v[]. I don't think v[4]==9 should be used when we know c[4]==10.
What happens for C(9)? We have no value for V9
how can u cut a 8 meter rod into 9 meter?
lol
Brilliant!!!!!
GOD
can i please get the source code for it ?
shud be easy 2 for loops -
int i = 0; i < n; i++
int j = 0; j < i; j++
www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/
Best
best
wooooowwww!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!11
i love u
thanks for wasting 15 minutes of my miserable life studying for algorithms exam
While this explanation is nice, it does not support multiple cuts (ex: 1,1,2 for 4). Although not applicable in this example, a lot of the time, the optimal price is based off of more than just 1 cut.
10Q
NO
not the millenial pause
Thank you!!