Given a rod of length n and a price array that includes prices of all pieces of rod smaller than N, determine the maximum profit obtained from cutting the rod into pieces and selling it.
Example:
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
Here, the length of the entire rod = 8 units.
So, we can divide the entire rod into multiple fashions like
Profit Earned
Selling the entire rod together as a single unit (of length 8) 1 piece * price[8] = Rs. 20
Cutting the entire length of rod into 1 unit length 8 pieces * price[1] = Rs. 8
Cutting the rod into 3 units + 5 units length price[3] + price[5] = 8 + 10 = Rs. 18
Cutting the rod into 2 units + 6 units length price[2] + price[6] = 5 + 17 = Rs. 22
and so on.
We will notice that the max profit that could be generated is Rs. 22.
Let's get started and learn various approaches to solve this problem.
The naive (or brute force) solution of this problem could be finding all possible configurations of different pieces and finding the highest profit possible configuration.
Cut ith length Subproblem.
So, cut ith length rod, store its price and calculate the price for the rest of the rod’s length via Recursion.
=> Profit Earned = price[i] + f(N - cut)
=> f(N) = max of {
1
price[0] + f(N - 1)
2
price[1] + f(N - 2)
3
price[2] + f(N - 3)
.
.
.
.
.
n
price[n - 1] + 0
}
=> Max profit earned = max(price[i] + f(n - cut)) where i = 0 to n - 1 (n = length of rod)
Note: The base case would be that if (n = 0) profit earned would be 0.
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
// Using recursive approach
public static int maxprofit(int[] price, int n){
// Base case
if (n <= 0) return 0;
// Profit earned
int ans = Integer.MIN_VALUE;
for (int i = 0; i < n; i++){
int cut = i + 1;
int curr_ans = price[i] + maxprofit(price, n - cut);
ans = Math.max(ans, curr_ans);
}
return ans;
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();
// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();
int profit = maxprofit(price,n);
System.out.println("Max Profit Earned "+ profit);
}
}
You can also try this code with Online Java Compiler
Time Complexity: O(N ^ N), i.e., exponential as we are covering all the prices(or cuts) possible for every price(or cut). Where ‘N’ is the length of the rod (or length of the price array).
We could optimize the time complexity of our previous approach by maintaining a dp array where dp[len] stores the max profit that could be earned from a rod of length ‘len’.
Since the recursive approach had a lot of overlapping subproblems, dp array would also help us avoid that repetitive work.
There are 2 approaches to solve this problem via dynamic programming:
APPROACH 2a: Via using Unbounded Knapsack
The structure of this problem matches with the knapsack as the price array resembles the value array of the knapsack, the length array (i.e 1 to N) resembles the weight array, and N resembles the max capacity of the knapsack.
Also, just like there, here too, we had to maximize the profit. At the same time, we have a choice whether to select a piece (i.e. cut at which piece - select or deselect a particular piece value).
Now, this problem is a variation of an unbounded knapsack and not a 0-1 Knapsack, as a particular piece’s length can be taken multiple times.
Example: For cutting a rod of length 2 (where n = 4): we can either piece it into 2 + 2 or 3+1
However, in 0-1 Knapsack, an item once taken cannot be chosen again.
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
// Using 2D dp approach
public static int maxprofit(int[] price, int[] length, int n, int maxlen, int[][] dp){
// 0 profit earned for 0 length and 0 price
if (n == 0 || maxlen == 0) return 0;
// Lookup in dp array
if (dp[n][maxlen] != 0) return dp[n][maxlen];
// Depending on profit, choose to take or discard maxlen
if (length[n - 1] <= maxlen) {
dp[n][maxlen] = Math.max(price[n - 1] + maxprofit(price, length, n, maxlen - length[n - 1], dp),
maxprofit(price, length, n - 1, maxlen, dp));
}
// length > maxlen => discard maxlen
else {
dp[n][maxlen] = maxprofit(price, length, n - 1, maxlen, dp);
}
return dp[n][maxlen];
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();
// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();
// Creating length array
int length[] = new int[n];
for (int i = 0; i < n; i++) {
length[i] = i + 1;
}
// Creating dp array
int[][] dp = new int[n + 1][n + 1];
int profit = maxprofit(price,length, n, n, dp);
System.out.println("Max Profit Earned for Rod Cutting:"+ profit);
}
}
You can also try this code with Online Java Compiler
Time Complexity: O(N ^ 2) as for each length we are traversing from 0 to that particular length to calculate our max possible profit for the current length.
Space Complexity: O(N ^ 2) as extra space for storing the max possible profit for each length of rod has been used.
Where ‘N’ is the length of the rod (or length of the price array).
APPROACH 2b: Optimised Approach
Now, let's try solving the problem in a 1-d dp array, hence optimizing itsspace complexity.
Earlier, we made a dp array with dimensions [price.length][length] i.e., the size of the price array and rod’s length array to calculate the max profit available for j-th length of the rod.
But now, we could also simply use a given price array and create a 1D dp array to calculate the max profit for i-th length, hence reducing our O(N * N) work to O(N) space complexity.
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
// Using 1D dp approach
public static int maxprofit(int[] price){
int n = price.length;
int[] dp = new int[n + 1];
// 0 profit earned for 0 length
dp[0] = 0;
for (int len = 0; len <= n; len++){
// Profit earned
int ans = Integer.MIN_VALUE;
for (int i = 0; i < len; i++){
int cut = i + 1;
int curr_ans = price[i] + dp[len-cut];
ans = Math.max(ans, curr_ans);
}
dp[len] = ans;
}
return dp[n];
}
public static void main (String[] args){
Scanner s = new Scanner(System.in);
System.out.println("Enter rod length");
int n = s.nextInt();
// Forming price array
int[] price = new int[n];
System.out.println("Enter prices for each length of rod");
for (int i = 0; i < n; i++) price[i] = s.nextInt();
int profit = maxprofit(price);
System.out.println("Max Profit Earned for Rod Cutting:"+ profit);
}
}
You can also try this code with Online Java Compiler
Time Complexity: O(N ^ 2) as for each length we are traversing from 0 to that particular length to calculate our max possible profit for current length.
Space Complexity: O(N) as extra space for storing the max possible profit for each length of rod has been used.
Where ‘N’ is the length of the rod (or length of the price array).
Dynamic programming is both a mathematical and computer programming method mainly used to optimize plain recursion.
What are two ways to apply dynamic programming?
The two ways to apply dp are bottom-up (i.e., iterative way) and top-down (i.e., using dp in recursion, commonly known as memoization).
What is the best case time complexity for the Rod Cutting Problem?
The best-case time complexity for Rod Cutting Problem is O(1), i.e., when the length of the rod is 0.
Conclusion
In this blog, we learned various approaches to the Rod Cutting Problem.
Rod Cutting Problem is a standard recursive problem that is optimized via dynamic Programming.
Here we use 1-d dynamic programming where dp[len] stores the max profit that could be earned from a rod of length “len.”
The optimized time complexity of this problem is O(N ^ 2) as for each length, we are traversing from 0 to that particular length to calculate our max possible profit for the current length.