Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Rod Cutting Problem

Objec­tive: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue rn obtain­able by cut­ting up the rod and sell­ing the pieces.

This is very good basic prob­lem after fibonacci sequence if you are new to Dynamic pro­gram­ming. We will see how the dynamic pro­gram­ming is used to over­come the issues with recursion(Time Complexity).

Given: Rod lengths are inte­gers and For i=1,2,…,n we know the price pi of a rod of length i inches

Exam­ple:

Length 1 2 3 4 5 6 7 8 9 10
Price 1 5 8 9 10 17 17 20 24 30
for rod of length: 4
Ways to sell :
•	selling length : 4  ( no cuts) , Price: 9
•	selling length : 1,1,1,1  ( 3 cuts) , Price: 4
•	selling length : 1,1,2  ( 2 cuts) , Price: 7
•	selling length : 2,2  ( 1 cut) , Price: 10
•	selling length : 3, 1  ( 1 cut) , Price: 9

Best Price for rod of length 4: 10

Approach:

Naive Approach : Recursion

  • There can be n-1 cuts can be made in the rod of length n, so there are 2n-1 ways to cut the rod.
  • So for every length we have 2 options either we cut it or not. we will con­sider both the options and choose the opti­mal out of it.

Code:

Time Com­plex­ity: O(2^n-1)
But this time com­plex­ity is very high since we are solv­ing many sub prob­lems repeatedly.

Rod Cutting Problem - Overlapping Sub problems

Rod Cut­ting Prob­lem — Over­lap­ping Sub problems

Dynamic Pro­gram­ming: Bottom-Up

Instead of solv­ing the sub prob­lems repeat­edly we can store the results of it in an array and use it fur­ther rather than solv­ing it again.

See the Code for bet­ter explanation:

Code:

Result: Max profit for length is 5:11

Rod Cutting Problem - Solution Matrix

Ref­er­ence: Link

You may also like...

  • Valentin

    I was just about to burst laugh­ing any sec­ond while the pro­fes­sor was explain­ing all the details of “rod cut­ting” in the class. Seri­ously, why did it have to be a “rod”?

  • Eugen Daroczy

    In the DP solu­tion, since there’s the option of not cut­ting the rod/rope at any given point, then we should not ini­tial­ize:
    int max = –1;

    but use instead the for­mula below, so we start off using the value of the entire sub­string. If the cuts add up to more value, that will be the par­tial solu­tion.
    int max = value[i-1];

    Sim­i­larly, for the recur­sive prob­lem we need so ini­tial­ize as:
    int max = value[length-1];