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.

Minmum Coin Change Problem

Problem Statement:

Every country has different type of bank notes and face value of each banknote is different.  Like in india we have banknote of 1, 2, 5, 10, 20 .... and so on :). So in today problem we only focus on lower bank note value not bigger.

Problem is if you have 1, 2, 5, 10 bank notes and you want to make change for the 17. There are multiple solution for that:

{10,5,2}

{5,5,5,2}

{10,5,1,1}

So we come across number of solution. Our aim is develop an algorithm with minimum number of coins So in our case we need a optimal solution  {10,5,2}.

We can write the problem in following manner:

Given a set of integer value Let {r1, r2 , r3... , rn } where r1 =1  and rj < rj+1 for 1<= j <= n-1, and a positive value W(17 from above). find a non negative set of integers which minimize.

n

∑xj

j=1

such that

n 

∑rjxj = W

j=1

Solution:

We will follow the approach of calculating change require for the all the x where x < w. 

Let suppose c[p] is minimum change (rupees change) require for the p rupees. For calculating the c[p] we need to calculate c[x] where x < p.

So what will be the c[p] ? 

c[p] = min : ri <= p { c[p - ri ] } + 1 if p > 0

            i                           0  if p = 0

Let understand the solution if we need a change for 7 rupees and we have coin for 1, 2 , 5.

We need to calculate c[7] with r = {1,  2,  5}.

First Calculate c[0] = 0  as p = 0

c[1] = min {c[1-1] } + 1  // We cannot consider 2 and 5 as the ri <= p condition does not met 2  > 1 and 5 > 1.

C[1] = min {0} + 1 = 1

C[2] = min {c[2-1],  c[2-2] }  + 1

c[2] = min {1 , 0} + 1

c[2] = 1 So we can calculate c[2] by just one coin 2

c[3] = min {c[3-1],  c[3-2] }  + 1

       = min {c[2] , c[1] } + 1

       = min {1 , 1} + 1

       = 1+1 = 2 // So we need two bank note for change of 3.

c[4] = min {c[4-1],  c[4-2] }  + 1

       = min {c[3] , c[2]} + 1

      = min {2, 1} + 1

     = 1+1 = 2 // right we need only two coin (2,2)

c[5] = min {c[5-1],  c[5-2] , c[5-5] }  + 1

       = min {c[4] , c[3] , c[0] } + 1

      = min {2 , 2 , 0} + 1

      = 1 // right now we have bank note 5 as ri <= p condition met where ri is bank note which is equal to 5 and p is also 5 we need change of 5.

c[6] = min {c[6-1],  c[6-2] , c[6-5] }  + 1

       = min {c[5] , c[4] , c[1]} + 1

      = min {1, 2, 1} + 1

      = 1 + 1 =  2 // (5, 1) or (1 , 5)

c[7] = min {c[7-1],  c[7-2] , c[7-5] }  + 1

       = min {c[6] , c[5] , c[2]]} + 1

       = min {2 , 1 , 1} + 1

      = 2 // (5,2 ) or (2, 5)

So our solution approach is right. 

How it works ? 

Just forget the problem and suppose you want to reach at value S with minimum addition of the values from the set {c1 ,  c2 ,  c3 , --- cn}. What approach you will take.

Greedy Approach:

Take the larger value from set try to add it two times or three times and check if it is larger than S. Then try to add lower value and so on. is it work every time ?
Try on this Sum = 30
{1, 15, 25}

No it will not work for the above case :).

Recursive Approach:

Let suppose you know the minimum number from the set require to make the sum S and it is following:

{C1, C2,  C2, C3}

We know one fact here if i do S-C3 the {C1, C2, C2} is the minimum numbers require for the sum C1+C2+C2.

Confusing ?

Let you have to make the sum 17 with the value {1, 3, 5}

then value is {1, 1, 5, 5, 5}

I am picking up the last value 5 and subtract it from 17. 17-5 = 12

and the remaining number is {1, 1, 5 , 5}.

So it is minimum number require for 12.

Now if i pick the last one again then {1, 1, 5} is minimum for 7.

So what i am doing here i am just subtracting the given value(17) from the set of to the number {1, 3, 5}.

If sum is 4 then we have {1, 3}

4-3 = 1 so we require only one value from the set that is {1} and it is true.

So can we apply this solution to our problem ?

Let suppose you have to make the coin change for 17 with the coin {1, 3, 5}.

Try to calculate C[17 - 5] , C[17 - 3] , C[17 -1] ? Which one is minimum add 1 into that. It is your solution :). So for this you need to calculate c[12], c[14] , c[16]. In this manner we need to calculate 

c[7],c[11], c[15] and so on.

Running Time:
Recursive approach will provide you the right solution but it will take longer time to execute. Because it will re compute the solution again again for the same number. Like for c[12] it will calculated three time one for c[17 - 5], c[15-3], c[13-1].

Can we improve that? yes the approach is dynamic programming.

Dynamic Approach:

We can solve any problem with dynamic programming if problem solution has following two attributes:

1) optimal substructure : If optimal solution is constructed from the optimal solution of subproblem then the solution has optimal sub structure.

2) overlapping subproblem :  If problem can be broken into sub problem which are used several times.

So both the attributes can be applied on our problem so we can solve our problem by dynamic programming.

So we Follow the same solution as explain above in Solution section.
Let suppose you have to calculate the minimum coins require for rupees j. Then you need to calculate minimum coin for all the value less than j(Optimal substructure).

Running Time:
We need to calculate minimum coin change for all the value less than j. So one loop is require for iteration to 1...j. In each value we need to check for the minimum value by iteration over all the coin value. So nested loop is require for the solution.

Complexity will be O(jl).
Where j is value for which minimum coin change need to be calculate.
l is length of the coin set.  


Code:

int findMinimumCoinChange(int rs, const int coinSetPtr [], size_t coinSetLength){

    int minCoinValues[rs+1];

    int finalSolutiuon = 0;

    memset(minCoinValues, -1, sizeof(minCoinValues));

    minCoinValues[0] = 0;

    //Calculating the solution from 1 to given rs.

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

        int solution[coinSetLength];

        memset(solution, -1, sizeof(solution));

        // All possible solution for the value i

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

            if(coinSetPtr [j] <= i){

                solution[j] = minCoinValues[i - coinSetPtr[j]] + 1;

            }

        }

        

        finalSolutiuon = -1;

        // Minimum Possible solution for the value i

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

            if(solution[k] > 0 ){

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

                    minCoinValues[i] = solution[k];

                }

            }

        }

        

        

    }

    return minCoinValues[rs];

}

You can download the full source code from the link

Now we are done with the coin change problem :).