Cutting a Rod – Dynamic Programming

There is a rod of length n inches. The rod can be cut into different pieces and can be sold. The price of different pieces is given in an array. The task is to find out the maximum value obtainable by cutting and selling the pieces.

Cutting a Rod Dynamic Programming

For example

We have a rod of length 10 inches and following gives the price of different pieces of the rod.

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

From the above table, if the size of piece is of length 1 inch, its price will be 1. If size 2 inch then price will be 3 and so on.

Now we have to find out the maximum value we can obtain by cutting rod and selling it.



Below is the recursive implementation

#include<iostream>
#include<limits.h>


using namespace std;

int maxValue(int array[], int size){
    
    if(size == 0)
      return 0;
      
    int maxV = INT_MIN;
    
    for(int i=0;i<size;i++)
      maxV = max(maxV, array[i] + maxValue(array,size-i-1));
      
    
    return maxV;
    
}


int main(){
    
    
    int array[]={1,3,6,7,7,10,15,16,17,20};
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<<"Maximum value: "<<maxValue(array,size);
    
    return 0;
}

Output

Maximum value: 21

 

Dynamic programming implementation to find maximum value

#include<iostream>
#include<limits.h>


using namespace std;

int maxValue(int array[], int size){
    
     int maxValues[size+1];
     maxValues[0] = 0;
     
     
     for(int i=1;i<=size;i++)
     {
         int maxV = INT_MIN;
         for(int j=0;j<i;j++){
             maxV = max(maxV, array[j] + maxValues[i-j-1]);
             }
        maxValues[i] = maxV;     
         
     }
    
    return maxValues[size];
    
}


int main(){
    
    
    int array[]={1,3,6,7,7,10,15,16,17,20};
    int size = sizeof(array)/sizeof(array[0]);
    
    cout<<"Maximum value: "<<maxValue(array,size);
    
    return 0;
}




Leave a Reply

Your email address will not be published. Required fields are marked *