Given a rod of length n and list of prices of rod of length i where 1 <= i <= n, find the optimal way to cut rod into smaller rods in order to maximize profit.

**Input:**

length[] = [1, 2, 3, 4, 5, 6, 7, 8]

price [] = [1, 5, 8, 9, 10, 17, 17, 20]

**Best:** Cut the rod into two pieces of length 2 each

to gain revenue of 5 + 5 = 10

**Cut Profit**

4 9

1, 3 (1 + 8) = 9

2, 2 (5 + 5) = 10

3, 1 (8 + 1) = 9

1, 1, 2 (1 + 1 + 5) = 7

1, 2, 1 (1 + 5 + 1) = 7

2, 1, 1 (5 + 1 + 1) = 7

1, 1, 1, 1 (1 + 1 + 1 + 1) = 4

The idea is very simple. We are given an array price[] where rod of length i has a value price[i-1]. One by one, we partition the given rod of length n into two parts of length i and n – i. We recuse for rod of length n – i but don’t divide rod of length i any further. Finally, we take maximum of all values. This yields the below recursive relation –

rodcut(n) = max { price[i – 1] + rodCut(n – i) } where 1 <= i <= n

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <bits/stdc++.h> using namespace std; // Function to find best way to cut a rod of length n // where rod of length i has a cost price[i-1] int rodCut(int price[], int n) { // base case if (n == 0) return 0; int maxValue = INT_MIN; // one by one partition the given rod of length n into two parts // of length (1, n-1), (2, n-2), (3, n-3), .... (n-1 , 1), (n, 0) // and take maximum for (int i = 1; i <= n; i++) { // rod of length i has a cost price[i-1] int cost = price[i - 1] + rodCut(price, n - i); if (cost > maxValue) maxValue = cost; } return maxValue; } // main function int main() { int length[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // dummy int price [] = { 1, 5, 8, 9, 10, 17, 17, 20 }; // rod length int n = 4; cout << "Profit is " << rodCut(price, n); return 0; } |

**Output: **

Profit is 10

The time complexity of above solution is O(n^{n}) and auxiliary space used by the program is O(1).

We have seen that the problem can be broken down into smaller subproblems which can further be broken down into yet smaller subproblems, and so on. Sp the problem has an **optimal substructure**. Let us consider recursion tree for rod of length 4.

As we can see, the same sub-problems (highlighted in same color) are getting computed again and again. So the problem also exhibits **overlapping subproblems**. We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are *Memo*ized rather than computed again and again. We will solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes T[i], which stores maximum profit achieved from rod of length i for each 1 <= i <= n. It uses value of smaller values i already computed.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <bits/stdc++.h> using namespace std; // Function to find best way to cut a rod of length n // where rod of length i has a cost price[i-1] int rodCut(int price[], int n) { // T[i] stores maximum profit achieved from rod of length i int T[n + 1]; // initalize maximum profit to 0 for (int i = 0; i <= n; i++) T[i] = 0; // consider rod of length i for (int i = 1; i <= n; i++) { // divide the rod of length i into two rods of length j // and i-j each and take maximum for (int j = 1; j <= i; j++) T[i] = max(T[i], price[j - 1] + T[i - j]); } // T[n] stores maximum profit achieved from rod of length n return T[n]; } // main function int main() { // int length[] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int price [] = { 1, 5, 8, 9, 10, 17, 17, 20 }; // rod length int n = 4; cout << "Profit is " << rodCut(price, n); return 0; } |

**Output: **

Profit is 10

The time complexity of above solution is O(n^{2}) and auxiliary space used by the program is O(n).

**References: **http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂