Objective: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algorithm to find the maximum revenue rn obtainable by cutting up the rod and selling the pieces.
This is very good basic problem after fibonacci sequence if you are new to Dynamic programming. We will see how the dynamic programming is used to overcome the issues with recursion(Time Complexity).
Given: Rod lengths are integers and For i=1,2,…,n we know the price pi of a rod of length i inches
Example:
| Length | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Price | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30 |
for rod of length: 4 Ways to sell : • selling length : 4 ( no cuts) , Price: 9 • selling length : 1,1,1,1 ( 3 cuts) , Price: 4 • selling length : 1,1,2 ( 2 cuts) , Price: 7 • selling length : 2,2 ( 1 cut) , Price: 10 • selling length : 3, 1 ( 1 cut) , Price: 9
Best Price for rod of length 4: 10
Approach:
Naive Approach : Recursion
- There can be n-1 cuts can be made in the rod of length n, so there are 2n-1 ways to cut the rod.
- So for every length we have 2 options either we cut it or not. we will consider both the options and choose the optimal out of it.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class RodCuttingRecursion { | |
| public static int profit(int[] value, int length) { | |
| if (length <= 0) | |
| return 0; | |
| // either we will cut it or don't cut it | |
| int max = –1; | |
| for(int i=0;i<length;i++) | |
| max = Math.max(max, value[i] + profit(value, length–(i+1))); | |
| return max; | |
| } | |
| public static void main(String[] args) { | |
| int[] value = { 2, 3, 7, 8, 9 }; | |
| int len = 5; | |
| System.out.println("Max profit for length is " + len + ":" | |
| + profit(value, len)); | |
| } | |
| } |
Time Complexity: O(2^n-1)
But this time complexity is very high since we are solving many sub problems repeatedly.
Dynamic Programming: Bottom-Up
Instead of solving the sub problems repeatedly we can store the results of it in an array and use it further rather than solving it again.
See the Code for better explanation:
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class RodCutting { | |
| public static int profitDP(int[] value, int length) { | |
| int[] solution = new int[length + 1]; | |
| solution[0] = 0; | |
| for (int i = 1; i <= length; i++) { | |
| int max = –1; | |
| for (int j = 0; j < i; j++) { | |
| max = Math.max(max, value[j] + solution[i – (j + 1)]); | |
| solution[i] = max; | |
| } | |
| } | |
| return solution[length]; | |
| } | |
| public static void main(String[] args) { | |
| int[] value = { 2, 3, 7, 8, 9 }; | |
| int len = 5; | |
| System.out.println("Max profit for length is " + len + ":" | |
| + profitDP(value, len)); | |
| } | |
| } |
Result: Max profit for length is 5:11
Reference: Link
I was just about to burst laughing any second while the professor was explaining all the details of “rod cutting” in the class. Seriously, why did it have to be a “rod”?
In the DP solution, since there’s the option of not cutting the rod/rope at any given point, then we should not initialize:
int max = -1;
but use instead the formula below, so we start off using the value of the entire substring. If the cuts add up to more value, that will be the partial solution.
int max = value[i-1];
Similarly, for the recursive problem we need so initialize as:
int max = value[length-1];