Rod Cutting - Dynamic Programming

We look at the rod cutting algorithm, and how profits can be maximized using dynamic programming.

[@rajeshseptember09]

this is by far the best explanation out there for the "rot cutting problem"

[@mentalgear3512]

I have been looking for a good video for this problem! This one explains it better than the rest.

[@Fnr2024]

Thank you so much for putting this together. This helped me a lot with my algorithms class.

[@CSBreakdown]

Frank Navarro Thanks for watching! Glad that it helped.

[@vaishnaviganseh2884]

I wish I had come across this video earlier and not after 5 hours of breaking my head on this problem. thanks mate

[@mayurkulkarni755]

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.

[@KENILDINESHPATELBCE]

One of the best tutorial for rod-cutting problem!!

[@sbshwetabhatt]

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. :-)

[@amazingmanish]

Man you made this a cakewalk. Thanks Bro. :-)

[@yanlinchen9559]

the best algorithm vid i ever watched

[@Javii96]

Great video. Helped me understand easier than the pseudo code in my textbook.

[@의진이-g8k]

you are the only one who rescued my life from this conception dynamic programming. this concept is good but devil :( :)

[@sachintsm8512]

This video is very good enough to understand well in rod cutting problem

[@presentlymine]

This video is my life saviour. EASY AND PERFECT explanation!

[@alialkhat9988]

Thank you so much. You have explain it way better then my instructor.. XD

[@fernchh]

It finally clicked, thankyou for the amazing video

[@TheAInfinity]

You are awesome. I get it now. Thank you so much sir.Here at the Matrix, we love you!!!

[@bungbang-e9n]

You gotta stay calm and composed when learning DP first. Its really messy. Thanks for the video. Great work

[@samirpanday4898]

nice advice thanks man

[@pramoddy3471]

thank you so much sir, it help full to my exam

[@Dev_God]

Clearly explained! Thank you so much for making this video!

[@jinhuang7258]

Very well explained. Thank you so much!

[@deepshree9777]

Thank You So Much!!! very well explained .. you really make it seem so easy .. now i am confident .. Keep up the good work ..

[@BangladesherBiratGorurHaat]

Great work and explaination Thank you

[@saisrisai9649]

Thank you soooo much sir. I have never been able to understand this. Please do on backtracking this way. Thanks again..

[@Brandonomics]

Thank you for the video!

[@ymeng7442]

Your videos are really helpful! Thank you very much!

[@rummanchowdhury3807]

Good explanation!

[@_Nikhil_Bagde_]

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.

[@_Nikhil_Bagde_]

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)

[@_Nikhil_Bagde_]

Original Problem was only using pure recursion and not memoization takes O(2^n) exponential time. DP rocks!

[@pranavn9245]

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.

[@iftekharjoy7118]

Sir karim is just awesome.upload more videos.

[@abdullahshakeel1344]

I'm looking for best one. so, here it is.

[@anuvrattiku3244]

Great Video, great explanation... Thanks

[@جمهوريةخرى]

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?

[@anonymoussloth6687]

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

[@flaggern7058]

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

[@SenthilBalas]

Nice explanation

[@juhithavaddineni1092]

lots of love to you 😀

[@eye23sun3]

GREAT JOB!!

[@zameetsabir543]

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 🥲❤

[@aliashoori8274]

I liked that first 5 mins - killed the complexity for me. Thanks.

[@ImGuti]

Great video !

[@ariashl]

that was really good tnx, Could you pls put presentation file for us too,that would be great

[@koenburg9751]

Yeah my professors' explaination was utter shite, thanks for making me understand!

[@MohsinJunaidEE]

thanks man superb jazallah

[@אריאלהשקרון]

you are so good!

[@TrangNguyen-jf1yj]

so so clear! tks!!

[@irtizamahmud6239]

awesome video tutorial. i like it very much. thank u.

[@psshatyTV]

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?

[@bartugkeskin6880]

I got it.Thank you so much.

[@blindprogrammer]

thanks! perfect explanation.

[@FreedomForKashmir]

thank you so much man you are great Much love and God bless

[@blindprogrammer]

Are you still alive? I think you were neutralized by the Indian military in Kashmir :/

[@mukeshphanse1586]

It is very useful thank you so much

[@dstgre]

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?

[@islamnuralam4402]

Thanks a lot

[@bigray712]

thanks, very methodical.

[@tonyaiello9811]

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.

[@rodrigocalderon8006]

exactly

[@iqraaslam7836]

Good Tutorial !

[@youmingxu1198]

Is it OK to do C(i) = { max{ C(k) + C(i-k) }, V(i) } where 1

[@anonymoussloth6687]

does this work?

[@gulnazbaloch29]

its an usefull video..thanks

[@jessiemanak9767]

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??

[@joshuawest3247]

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.

[@pranavn9245]

@@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.

[@kirancobi]

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.

[@Tierprot]

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

[@kishor0907054]

helpful, thank you

[@jimitshah7636]

very nice

[@SolzheBitsyn]

thanks

[@manojprajapati932]

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

[@xiaoxin0430]

Thanks a lot!

[@architguleria989]

The approach used here is bottom up not top down ....

[@WYO_Dirtbag]

My professor is not specifying if it has to be top down or bottom up on my test so I will choose this way.

[@user-px2jq1bm8t]

Why bottom up

[@chrisklecker]

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.

[@akashdutta1620]

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?

[@eye23sun3]

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!

[@prajwalacharya6048]

Awesomee!!!! Like really awesome

[@avinandanganguly4466]

In the formula what the hell is 'k'?

[@rachitgarg9766]

Great!

[@KienNguyen-uv7wj]

thank you.

[@Shehzad-Ahmed]

Thnx buddy .....

[@How2GetFreeGiftCard]

What happens for C(9)? We have no value for V9

[@murtazanihal4181]

how can u cut a 8 meter rod into 9 meter?

[@shivamgupta-tk2dd]

lol

[@haseebhashmi4338]

Thanks sir :)

[@lzmkalos]

GOD

[@quanm1925]

Best

[@zunairamarwat966]

can i please get the source code for it ?

[@aprofromuk]

shud be easy 2 for loops - int i = 0; i < n; i++ int j = 0; j < i; j++

[@akhileshjoshi8484]

www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

[@vinodbirla765]

Thank you so much (Y)

[@nileshjoshi5358]

I think max value of k=floor(i/2) should be enough. K do not required to go all the way to i.

[@christernilsson1]

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.

[@deepakd6015]

Shouldn't it be max{Ck+C(i-k)} ?

[@bd189a55]

Yes, I think it should be max{Ck+C(i-k)}.

[@rickdev]

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 ;)

[@bd189a55]

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.

[@chrisklecker]

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.

[@joshuawest3247]

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.

[@murtazanihal4181]

best

[@yoganandareddy4721]

wooooowwww!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!11

[@morales9312]

Brilliant!!!!!

[@toprecbot]

i love u

[@alanperaza9594]

10Q

[@michaelm4110]

thanks for wasting 15 minutes of my miserable life studying for algorithms exam

[@tristanhurley9071]

NO

[@moatazabdelraouf4059]

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.

[@nathanzimet434]

not the millenial pause

[@esraamohamed5601]

Thank you !

[@wiambenhammou9942]

Thank you!!