Cut a Road with Maximum Profit (Dynamic Programming)

Problem Statement:

Let suppose you have a rod of some length x inches and given a array of prices that contain prices of all size less than x. You need to calculate the maximum price value by cutting the road and selling the pieces.

Let understand with example. Suppose you have a rod of length 8 inch and the value of differnet pieces is given below:

Length	1	2	3	4	5	6	7	8
Price	1	5	8	9	10	17	17	20

   

So If we do not cut the road then we can sell it with price 20 rs. is there any better solution so that price can be increase ?

If we cut it in equal piece (4, 4) then we have price 18. 9+9.

So from the above table if we cut it in 6,2 then we have maximum price 22. So it is our solution.

Solution Approach:

Brute-Force Approach:

Brute force approach is simple you need to calculate each pair cost and select the maximum one. It is simple but take long time to execution. Running time for the brute force approach is exponential.

Explanation of the approach:

Let suppose maximum price for length L is M[L]. To calculate M[L] we will calculate the maximum price M[X] for all X such that X < L.

So start with M[1] = 1
M[2] = 5 because if go for p[1] + p[1] =  2 which is less than 5. So here we are doing max of all the cases.
M[3] = max(p[1]+p[1]+p[1], p[2]+p[1], p[3])
 = max(1+1+1, 5+1, 8)
 = max(3, 6, 8)
 = 8
M[4] = max(p[1]+p[1]+p[1]+p[1], p[2]+p[2], p[3]+p[1],  p[2]+p[1]+p[1] , p[4])
        = max(4, 5+5, 8+1, 5+1+1,  9)
       = max(4, 10, 9, 7, 9)
       = 10
M[5] = max (p[4]+p[1],  p[3]+p[2] ,  p[3]+p[1]+p[1],  p[2]+p[2]+p[1],  p[2]+p[1]+p[1]+p[1],  p[1] +p[1] +p[1] +p[1] +p[1] , p[5])
       = max(11, 13,  10,11,  8, 5, 10)
       =13 (3, 2) is the best for cut a road of length 5.

Do we need to examine all of this it is also very tedious task. So is there any better solution ?

Adding Existing Max Price To Solution:

When we are calculating M[4] maximum price for length 4 we already know the price of M[3] , M[2] M[1] but we are not using that in above approach :(.

So when we are calculating M[4] we start with  adding price for length 1 So length 3 has left. Then there are various options for length 3 we tried in above example like p[1] + p[1]+p[1] , p[2] + p[1] , p[3]. But we forget we already know the M[3] for the length 3 and no options will be better than M[3]. So why not use that :).

Explanation of the approach:

M[0] = 0

M[1] = 1

M[2] = max (p[1] + M[1] , p[2]+M[0])

M[3] = max (p[1] + M[2], p[2]+M[1],p[3]+M[0])

M[4] = max(p[1]+M[3], p[2]+M[2], p[3]+M[1], P[4]+M[0])

and So on.

It is simple approach and easier to calculate.

So in mathematical term we can write this as:
M[n] = max(p[i]+m[n-i-1])
             0<=i<n

Recursive Approach:

It is similar to the approach we discussed in the coin-change problem of dynamic programming.
We will apply the above formula to calculate the maximum price. So for M[8] it will calculate the M[7], M[6], M[5] and So on.
But there is one problem in recursion a same M[i] will be calculate again and again. Suppose you are calculating M[4] then following is recursion tree:

So in the above tree you can see M[2] is calculated 2 times. For the larger problem the same max price is calculated multiple time.

We can use dynamic programming for the better run time.

Dynamic Programming  Approach:

We will save the previous M[i] value for calculating the M[i]. In this case we will start from 0 to calculate maximum benefit and then reach to M[8] as explained above in Adding Existing Max Price To Solution section.

We forgot one thing to solve a problem with dynamic programming it must have two attributes:

1) Optimal substructure : Yes we are solving it by first solving the small solution like M[0] , M[1]
2) Overlapping Subproblem: We have seen in above case a same M[2] is calculated multiple time.

So we can apply dynamic programming here and following is solution with dynamic programming:

Following is solution with C programming:

int cutroad(int price[], int rodLength){

    int maxBenefit[rodLength + 1]; // Store the max benefit for all the length 0...8 in our case

    int solution[rodLength];     // use for calculating all the possible result for each length 1...8

    int finalSolution = -1;

    memset(maxBenefit, 0, rodLength);

    //Start from the length 1 to 8. This loop used for calculate the maxbenefit for the lenght 1 to 8.

    for (int i = 1;  i < rodLength +1; i++) {

        memset(solution, -1, rodLength);

        //Loop used fo calculate possible solution for particular lenght like for 2.M[2] = max (p[1] + M[1] , p[2]+M[0])

        for (int j=0; j < i; j++) {

            solution[j] = price[j]+maxBenefit[i-j-1];

        }

        // Calculate max benefit from all the possible solution.

        for (int k=0; k< i; k++) {

            if(solution[k] >= 0){

                if (finalSolution == -1 || finalSolution < solution[k]){

                    finalSolution = solution[k];

                }

            }

        }

        maxBenefit[i] = finalSolution;

    }

    return maxBenefit[rodLength];

}

You can download full source code from the link.