Rod Cutting Problem using Dynamic Programming

Algorithms

Problem: We are given a rod of length l and an array that contains the prices of different sizes less than l. Our task is to piece the rod in such a way that the revenue generated by selling them is maximum.

For example, consider following given problem:

Rod cutting problem

We could get a maximum revenue of 18 if we cut the rod into two pieces of length 6 and 1.

Revenue table of rod cut

We can solve this problem using recursion and further optimize it using dynamic programming.

Solution using Recursion (Naive Approach)

We can cut a rod of length l at position 1, 2, 3, …, l-1 (or no cut at all).

price of rod cut piece

In each case, we cut the rod and sum the prices of the pieces. We compare the total revenue of each case and get the one which gives the maximum profit.

i.e., max(price[l-i] +price[i]) for all i in {0, 1 … l-1}

Because every piece after the cut is a rod itself, we recursively repeat the same process to get the max possible revenue for each piece.

i.e., max(rod_cutting(l-i]) +price[i]) for all i in {0, 1 … l-1}

Here is the implementation of the recursive solution in Python, C++ and Java:

Python

import sys

#list of prices corresponding to the peices of index length 
price = [0, 1, 5, 8, 9, 10, 17, 17, 20];

#recursive Solution
def rod_cutting(l):
  #base condition
  if(l==0):
    return 0

  #variable to store the maximum revenue
  max_value = -sys.maxsize
  
  #loop for all possible cut cases
  for i in range(1, l+1):
    #store the max revenue of all cut cases
    max_value =  max(max_value, rod_cutting(l-i)+ price[i])

  return max_value

#Driver code
if __name__ == '__main__':
  print("Max Revenue: ",rod_cutting(7))

C++

#include <iostream>
using namespace std;

//array of prices corresponding to the pieces of index length 
int price[]= {0, 1, 5, 8, 9, 10, 17, 17, 20};

//recursive function
int rod_cutting(int l){
    //base condition
    if(l==0)
      return 0;

    //variable to store max revenue,
    //initially have minimum possible integer value
    int max_value = INT32_MIN;

    //loop for all possible cut cases
    for(int i=1; i<=l; i++){
      //store the max revenue of all cut cases
      max_value = max(max_value, rod_cutting(l-i)+ price[i]);
    }

    return max_value;
}

//Driver code
int main() {
  cout << "Max Revenue: " << rod_cutting(7);
  return 0;
}

Java

class Main {
  //array of prices corresponding to the pieces of index length i.e, price table
  static int price[]= {0, 1, 5, 8, 9, 10, 17, 17, 20};

  //Driver code
  public static void main(String[] args) {
    System.out.println("Max Revenue: "+rod_cutting(4));
  }

  //Recursive function
  public static int rod_cutting(int l){
    //Base condition
    if(l==0)
      return 0;

    //variable to store max revenue,
    //initially have minimum possible integer value
    int max_value = Integer.MIN_VALUE;

    //loop for all possible cut cases
    for(int i=1; i<=l; i++){
      //store the max revenue of all cut cases
      max_value = Math.max(max_value, rod_cutting(l-i)+ price[i]);
    }

    //return the max value
    return max_value;
  }
}
Max Revenue: 18

The time complexity of the above solution is O(nn).

The reason for such high time complexity is that the recursive solution computes overlapping subproblems multiple times.

For instance, when computing the max price of length=7, the price of some of the preceding lengths is calculated multiple times.

recursive calls in rod cutting recursive solution

We can leverage dynamic programming to significantly reduce the computational task of the recursive solution.

Solution using Dynamic Programming (Efficient Approach)

The idea is to store the solution of subproblems into a memo table (array) so that we can reuse them without computing it again i.e., store the max price of each length into an array when they are calculated for the first time.

rod cutting problem recursive calls with DP

Here is the implementation of the solution of the rod cutting problem using Dynamic Programming:

Python

import sys

#list of prices corresponding to the peices of index length 
price = [0, 1, 5, 8, 9, 10, 17, 17, 20]
#memo table
max_price = [-1 for x in range(len(price))]

#recursive funtion
def rod_cutting(l):
  #base condition
  if(l==0):
    return 0

  #check memo table if it already has the max price for length 'l'
  #if yes then return the value otherwise continue computing the max price for 'l'
  if max_price[l] != -1:
    return max_price[l]

  #variable to store the maximum revenue
  max_value = -sys.maxsize
  
  #loop for all possible cut cases
  for i in range(1, l+1):
    #store the max revenue of all cut cases
    max_value =  max(max_value, rod_cutting(l-i)+ price[i])
  
  #update the max price for 'l' in the memo table
  max_price[l] = max_value
  return max_price[l]

#Driver code
if __name__ == '__main__':
  length = 7
  print("Max Revenue: ",rod_cutting(length))

C++

#include <iostream>
using namespace std;

//array of prices corresponding to the peices of index length 
int price[]= {0, 1, 5, 8, 9, 10, 17, 17, 20};
//memo table to store max price each lengths
int max_price[sizeof(price)/sizeof(price[0])];

//recursive function
int rod_cutting(int l){
    //base condition
    if(l==0)
      return 0;

    //check memo table if it already has the max price for length 'l'
    //if yes then return the value otherwise continue computing the max price for 'l'
    if(max_price[l] != 0)
      return max_price[l];

    //variable to store max revenue,
    //initially have minimum possible integer value
    int max_value = INT32_MIN;

    //loop for all possible cut cases
    for(int i=1; i<=l; i++){
      //store the max revenue of all cut cases
      max_value = max(max_value, rod_cutting(l-i)+ price[i]);
    }

    //store the max price for 'l' in the memo table
    max_price[l] = max_value;

    //return the max price 
    return max_price[l];
}

//Driver code
int main() {
  int length = 7;
  cout << "Max Revenue: " << rod_cutting(length);
  return 0;
}

Java

class Main {
  //array of prices corresponding to the peices of index length i.e, price table
  static int price[]= {0, 1, 5, 8, 9, 10, 17, 17, 20};
  //memo table to store max price each lengths
  static int max_price[] = new int[price.length];

  //Driver code
  public static void main(String[] args) {
    int length = 7;
    System.out.println("Max Revenue: "+rod_cutting(length));
  }

  //Recursive function
  public static int rod_cutting(int l){
    //Base condition
    if(l==0)
      return 0;

    //check memo table if it already has the max price for length 'l'
    //if yes then return the value otherwise continue computing the max price for 'l'
    if(max_price[l] != 0)
      return max_price[l];

    //variable to store max revenue,
    //initially have minimum possible integer value
    int max_value = Integer.MIN_VALUE;

    //loop for all possible cut cases
    for(int i=1; i<=l; i++){
      //store the max revenue of all cut cases
      max_value = Math.max(max_value, rod_cutting(l-i)+ price[i]);
    }

    //store the max price for 'l' in the memo table
    max_price[l] = max_value;

    //return the max price 
    return max_price[l];
  }
}

Output:

Max Revenue: 18

The time complexity of this solution is O(n2). Since we are using an extra array for memorization, the space complexity for the program is O(n).

In this tutorial, we learned to solve the rod cutting problem using the concept of dynamic programming in C++, Java, and Python.

Leave a Reply

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