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 ith 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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.