Q:

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

mahmoud2506
Save to bookmark
|
2022-04-30
|
  283 
0

Rod Cutting

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.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given an array of integers where each element repr... >>
<< Given n dice each with m faces, numbered from 1 to...