Description: You are given a rod of length n inches and an array of prices that contains prices of all pieces of rod of size smaller than n. Your task is to write a function to find the maximum revenue that can be generated by cutting the rod and selling the pieces

Example:

Length of rod: 8

length |  1 2 3 4  5   6   7    8

price    | 1 5 8 9 10 17 17 20

Maximum revenue: 22 (from pieces of size 2 & 6)

Solution

Let maxCutRod(n) be the required (best possible price) value for a rod of length n. maxCutRod(n) can be written as following.

•       maxCutRod(n) = max(price[ i ] + maxCutRod(n-i-1)) for all i in {0, 1 .. n-1}

Algorithm:

 
maxCutRod( n)
{
   let val0….n] be a new array
   val[0] = 0;
   /*Build the table val[] in bottom up manner*/
   for (i = 1 to n)
   {
    max_val = INT_MIN;
       for (j= 0 to i)
         max_val = max(max_val, price[j] + val[i-j-1]);
       val[i] = max_val;
   }
   return val[n];
}
 

C Implementation:

/*function to get the maximum of two integers */
int max(int a, int b) { return(a > b)? a : b;}
 
/* Funtion to find maximum price for a rod of length n */
 
int maxCutRod(int price[], int n)
{
 int val[n+1];
 val[0] = 0;
 int i, j;
 
/* Build the table val[] in bottom up manner */
 
   for(i = 1; i<=n; i++)
   {
       int max_val = INT_MIN;
       for(j = 0; j < i; j++)
         max_val = max(max_val, price[j] + val[i-j-1]);
       val[i] = max_val;
   }
 
   return val[n];
}

 

Time Complexity:

O(n^2)

Go to top