Cutting rods problem

Tags:

Given a rod of length ‘n’ units and list of prices of pieces of lengths ‘1’ to ‘n’, the problem is to determine the maximum value that can be obtained by cutting the rod and selling the pieces.
For eg.

Input:
Rod is of length 4 and list of prices is:
Piece length 1 2 3 4
Price 2 5 7 8
Output:
10
Explanation:
The maximum value that can be obtained in this case is ‘10’ by cutting the rod in pieces of length {2, 2}.

Thought process

One might get tempted to use a Greedy approach for solving problems where we need to find either minimum or maximum values, but remember that for the Greedy approach one has to give proof of its correctness as it takes just a single example/test case to prove that Greedy approach fails. Hence in general such problems are solved using DP.
Solution Approach:
To find the maximum value using the price list and length of the rod, instead of considering the extremes (like we do in Greedy) from the given input, we consider all the input values. Meaning, in a Greedy approach one might consider cutting the rod in pieces with the highest available price only so that he can obtain the maximum value, but this approach fails in case of the example above.

Hence to find the maximum value we will consider cutting the rod in pieces of all possible lengths, i.e. for a rod of length ‘4’, if get_max_val(price_list, rod_length = 4) gives the maximum value, then:
We’ll first consider making a cut at length 1: This gives us a piece of length 1 and we can sell this piece to get value 2.
Now we are left with the remaining rod of length 4 – 1 = 3. The problem now reduces to finding the maximum value that can be obtained from a rod of length 3 with the same input price list. The total value that can be obtained in this configuration will be:

2 + get_max_val(price_list, rod_length = 3).

Similarly, we can make a cut at length 2: this gives us a piece of length 2 and we can sell this piece to get value 5.

Now we are left with the remaining rod of length 4 – 2 = 2. The problem now reduces to finding the maximum value that can be obtained from a rod of length 2 with the same input price list. The total value that can be obtained in this configuration will be:

5 + get_max_val(price_list, rod_length = 2).

Also, we can make a cut at length 3: This gives us a piece of length 3 and we can sell this piece to get value 7.

Now we are left with the remaining rod of length 4 – 3 = 1. The problem now reduces to finding the maximum value that can be obtained from the rod of length 1 with the same input price list. The total value that can be obtained in this configuration will be:

7 + get_max_val(price_list, rod_length = 1).

We can also sell the complete rod of length ‘4’ as it is, which will fetch us the total value => 8

For each sub-problem, we’ll take a similar approach of cutting the current piece of a rod into pieces of length ranging from ‘1’ to ‘current rod length’. We keep cutting the rod and solving the resulting sub-problems till the length of the rod reaches zero. While trying out these different configurations we will keep a track of the maximum of the total value of each configuration.

The approach discussed above shows that this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

Let’s try to implement this using recursion:
C++:

#include <iostream>
#include <vector>
using namespace std;
 
int get_max_value(vector<int>& price_list, int  rod_length)
{
      if(rod_length <= 0)
            return 0;
      int max_value = 0;
      for(int i=0; i<rod_length; i++)
      {
            max_value = max(max_value, 
                    price_list[i] 
                  + get_max_value(price_list, rod_length - i - 1)
            );
      }
      return max_value;
}
 
int main(void)
{
      vector<int> price_list{2, 5, 7, 8};
      int rod_length = 4;
      cout<<get_max_value(price_list, rod_length)<<endl;      
      return 0;
}

Java:

import java.io.*;
 
class rod_cutting
{
    static int max(int a, int b)
    {
        return (a < b) ? b : a;
    }
    
    static int get_max_value(int price_list[], int rod_length)
    {
        if (rod_length <= 0)
            return 0;
            
        int max_value = 0;
        
        for(int i=0; i<rod_length; ++i)
        {
            max_value = max(max_value, 
                       price_list[i] 
                     + get_max_value(price_list, rod_length - i - 1)
            );
        }
        
        return max_value;
    }
    
    public static void main(String args[])
    {
        int price_list[] = new int[] {2, 5, 7, 8}; 
        int rod_length = price_list.length; 
        System.out.println(get_max_value(price_list, rod_length)); 
    }
};

But this recursive implementation has exponential time complexity. Let’s have a look at the function call tree to understand the reason behind this:
rod cutting problem

In this example of finding max value for a rod of length = 4 and a list of prices for its pieces, subproblems such as get_max_value(price_list, 2) and get_max_value(price_list, 1) are calculated repeatedly. Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems.
As the two properties required for using Dynamic Programming: optimal substructure and overlapping subproblems hold, we can use DP for this problem. Unlike recursion, Dynamic Programming uses a bottom-up approach.

Dynamic Programming Approach

In DP we start calculating from the bottom and move up towards the final solution. The solutions of all subproblems are stored in a 2D array / DP table so that they can be reused when required.

#include <iostream>
#include <vector>
using namespace std;
 
int get_max_value(vector<int>& price_list, int  rod_length)
{
    int dp_table[rod_length+1][rod_length+1] = {};
    
    for (int i = 1; i <= rod_length; i++)
    {
        for (int j = 1; j <= rod_length; j++) 
        {
            if(j >= i)
            {
                dp_table[i][j] = max(dp_table[i-1][j],
                    price_list[i-1] + dp_table[i][j-i]);
            }
            else
            {
                dp_table[i][j] = dp_table[i-1][j];
            }
        }
    }
    
    return dp_table[rod_length][rod_length];
}
 
int main(void)
{
      vector<int> price_list{2, 5, 7, 8};
      int rod_length = 8;
      court<< get_max_value(price_list, rod_length)<<endl;      
      return 0;
}

The time complexity of the solution is O(n2) along with space complexity of O(n2) Where n is rod length.

The space complexity of the DP code can be reduced by skipping storing solutions of each subproblem so that instead of a 2D array we can work with a 1D array.

With a 2D array, we were storing solutions for subproblems that have a particular rod length with a subset of given price_list, but instead of this for a particular rod length we can compare total values obtained from all subproblems and storing only the maximum value, this way using a 1D array suffices.
But also note that a question, if asked, that what cuts were actually made to get the maximum value, cannot be answered with a 1D array solution. In 2D array, we can traverse back starting from dp_table[rod_length][rod_length] and check if the value at the current cell is calculated from the same row and if that’s the case then the current row number is considered as one of the piece lengths that were cut to get the maximum value.

import java.io.*;
 
class rod_cutting
{
    static int max(int a, int b)
    {
        return (a < b) ? b : a;
    }
    
    static int get_max_value(int price_list[], int rod_length)
    {
        int dp_table[] = new int[rod_length+1];
        dp_table[0] = 0;
        
        for (int i=1; i <= rod_length; ++i)
        {
            int max_value = 0;
            
            for (int j=0; j < i; ++j)
            {
                max_value = max(max_value, 
                     price_list[j] + dp_table[i - j - 1]);
            }
            dp_table[i] = max_value;
        }
        
        return dp_table[rod_length];
    }
    
    public static void main(String args[])
    {
        int price_list[] = new int[] {2, 5, 7, 8}; 
        int rod_length = price_list.length; 
        System.out.println(get_max_value(price_list, rod_length)); 
    }
};

The time complexity remains same O(n2) but the space complexity reduces to O(n) where n is rod length.

This article is contributed by Bhushan Aggrawal.