Home » Interview coding problems/challenges

Rod Cutting

Rod Cutting: Here, we are going to learn how to maximize profit by cutting rod with dynamic programming? Submitted by Radib Kar, on February 18, 2020

Description

In this article we are going to see how to maximize profit by cutting rod with dynamic programming? This is a classic DP problem featured in many interview rounds of Amazon, Samsung etc.

Problem statement

Given a rod of length N inches and an array of prices that contains prices for all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

    Input:
    First input line consists of N, 
    denoting the size of array. 
    Second line of price of ith length piece.
    
    Output:
    Print maximum price that can be obtained by selling the pieces.

Example

    Input:
    Length of rod: 8

    Prices of pieces:
    1 5 6 9 12 15 13 20

    Output:
    maximum price that can be obtained: 20

Explanation

Let us first understand the input format

Each element in the array represent price of length i where i is the index (considering 1-indexing).

So, for the above example:

    Price of length 1: 1  (arr[0])
    Price of length 2: 5  (arr[1])
    Price of length 3: 6  (arr[2])
    Price of length 4: 9  (arr[3])
    Price of length 5: 12 (arr[4])
    Price of length 6: 15 (arr[5])
    Price of length 7: 13 (arr[6])
    Price of length 8: 20 (arr[7])

Now, the thing is cutting the rod recursively. Like you have to option;

1. Cut of i^th length and recur for remaining
2. Else don't cut of that length.

The recursive function can be written as:

    f(n) = maximum (f(i)+f(n-i))  where 1 ≤ i< n

In the above example, it's found that if we don't cut into pieces, if we sell the whole rod as 1 piece, then it would maximize profit to 20. All other options will lead to less amount of profit.

Also, if we make 4 pieces of length 2, would have same profit, 20.

Solution Approach

Let's convert the above recursion in to dynamic programing.

The sub-problem can be to solve for rod of length i where 1<=i<=n and we need to store the results of this sub-problems in a array, namely DP

1. Declare DP[n+1]
2. DP[0]=0 as the result for rod length 0 is 0.
3. Now we need to calculate DP[i] which would be results for rod length i (subproblems)
4. As a base case, initialize DP[i] with arr[i-1] which is the result if we don't cut into smaller pieces and sell the whole rod(piece of length i).

   for(int i=1;i<=n;i++)
       dp[i]=a[i-1];
   

   The reason behind dp[i]=arr[i-1] not arr[i] because in DP array we are following 1-indexing( like for n=1 it's DP[1]) and for arr we are following 0-indexing(for n=1, arr[0])
5. Now, calculate DP[i] which will be maximum profit for sub problem with length i
   Here we will use the recursive relation mentioned above
   To calculate DP[i],for 2≤i≤n,
   if i is 1 that follows base case,no more pieces to cut down

       for j=1 to i-1
           dp[i]=maximum(dp[j]+dp[i-j])
       end for
   

6. DP[n] is the final result which is maximum profit for rod length n.

We could have calculated through the recursive function, but needless to say that the recursion tree would have overlapping sub-problem resulting to exponential time complexity. Hence, we converted the recursion into DP and solved.

C++ Implementation

#include <bits/stdc++.h>

using namespace std;

int rodcutting(vector < int > a, int n) {
  int dp[n + 1];
  dp[0] = 0;

  for (int i = 1; i <= n; i++)
    dp[i] = a[i - 1];
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      if (dp[i] < dp[j] + dp[i - j])
        dp[i] = dp[j] + dp[i - j];
    }
  }
  return dp[n];
}

int main() {
  int n, item;

  cout << "Enter rod length:\n";
  scanf("%d", & n);
  cout << "Enter prices for the pieces of ith length:\n";
  vector < int > a;
  for (int j = 0; j < n; j++) {
    scanf("%d", & item);
    a.push_back(item);
  }

  cout << "Maximum profit can be earned is: " << rodcutting(a, n) << endl;

  return 0;
}

Output

RUN 1:
Enter rod length: 
8
Enter prices for the pieces of ith length:
1 5 6 9 12 15 13 20
Maximum profit can be earned is: 20

RUN 2:
Enter rod length: 
7
Enter prices for the pieces of ith length:
4 5 6 3 21 15 13 
Maximum profit can be earned is: 29