Given a rod of length ln and an array of prices for different lengths (i) of the rod, where 1 <= i <= n, find the optimal way to cut the rod into smaller prices to maximise profit.
Input:
piecesLength [] = {1, 2, 3, 4, 5, 6, 7, 8}
piecesPrice[] = {1, 5, 8, 9, 10, 17, 17, 20}
rodLength = 8
Output: 22
Solutions
Method 1: Recursion
The "Rod Cutting Problem" is similar to an unbounded knapsack problem; the length of the rod can be compared to the "capacity" of a knapsack, and the "length" and "price" of pieces can be compared to the "weight" and "value" of items in a knapsack.
The idea is to recursively generate all combinations of different pieces and find the highest-priced configuration.
While considering a piece, we have one of the following two choices:
Choice 1: The piece is included in the optimal subset—decrease the length by the piece length and increase the profit by its price.
Choice 2: The piece is not included in the optimal set—don't do anything.
While picking a piece, also make sure that its length is less than or equal to the remaining length of the rod.
Complexity
The time complexity of the above recursive solution is exponential (2^n).
In addition, O(n) auxiliary stack space was used for the recursion stack.
Method 2: Memoization
The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.
We can see that in each recursive call only the value of "n" and "ln" (length) changes, so we can store and reuse the result of a function(..n, ln..) call using a "n * ln" 2-D array.
The 2-D array will store a particular state (n, ln) if we get it the first time.
Now, if we come across the same state (n, ln) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.
Complexity
The time complexity of this solution is (n * ln).
In addition, O(n * ln) auxiliary space was used by the table.