This Java program solves the rod cutting problem using dynamic programming. The goal is to maximize profit by cutting a rod of a given length into pieces, with each piece having a specific price.
Java Program
public class RodCutting {
// Function to calculate the maximum profit by cutting the rod
public static int maximizeProfit(int[] prices, int rodLength) {
// DP array where dp[i] represents the maximum profit for a rod of length i
int[] dp = new int[rodLength + 1];
// Initialize the DP table with 0 profit for a rod of length 0
dp[0] = 0;
// Build the dp table in a bottom-up manner
for (int i = 1; i <= rodLength; i++) {
int maxProfit = Integer.MIN_VALUE;
// Try cutting the rod at every length and take the maximum profit
for (int j = 0; j < i; j++) {
maxProfit = Math.max(maxProfit, prices[j] + dp[i – j – 1]);
}
dp[i] = maxProfit;
}
// The maximum profit for a rod of length rodLength is stored in dp[rodLength]
return dp[rodLength];
}
public static void main(String[] args) {
// Example: Prices of pieces of rod of different lengths
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int rodLength = 8;
// Solve the rod cutting problem
int maxProfit = maximizeProfit(prices, rodLength);
System.out.println(“Maximum profit by cutting the rod is: ” + maxProfit);
}
}
Explanation of the Program Structure
This program solves the rod cutting problem using dynamic programming. The problem involves cutting a rod of a given length into smaller pieces to maximize profit, with each piece having a specific price.
- maximizeProfit function: This function implements the dynamic programming solution for the rod cutting problem. It takes two inputs: an array
prices[]where each element represents the price of a rod of lengthi+1, and an integerrodLengthwhich is the length of the rod to be cut. - Dynamic Programming Array (dp): The array
dp[i]stores the maximum profit that can be obtained by cutting a rod of lengthi. The array is filled in a bottom-up manner by trying to cut the rod at every possible length and calculating the maximum profit for each length. - Main logic: The program iterates through all lengths of the rod, and for each length, it tries cutting the rod at every possible position to calculate the profit. The final result,
dp[rodLength], contains the maximum profit for the full length of the rod. - Base case: When the rod length is 0, the profit is 0 (since no cuts are made). This is represented by initializing
dp[0]to 0. - main function: This function initializes a sample set of prices for different lengths of the rod and calls the
maximizeProfitfunction to compute and print the maximum profit that can be obtained by cutting the rod.
Step-by-Step Process:
- We initialize a dynamic programming array
dpof size(rodLength+1), where each elementdp[i]stores the maximum profit for a rod of lengthi. - We iterate through all possible lengths of the rod, from 1 to
rodLength. For each length, we try every possible cut (from 1 to the current length) and update the DP table with the maximum profit. - The base case handles when the rod length is 0, in which case the profit is 0.
- The final result, stored in
dp[rodLength], represents the maximum profit for the full length of the rod.
Example:
Consider the following prices for rods of different lengths:
Prices: {1, 5, 8, 9, 10, 17, 17, 20}
Rod length: 8
In this case, the maximum profit is 22, obtained by cutting the rod into two pieces of length 2 and 6. The program will output:
Maximum profit by cutting the rod is: 22
Conclusion:
This Java program efficiently solves the rod cutting problem using dynamic programming. The time complexity of this solution is O(n^2), where n is the length of the rod. This approach ensures that all possible ways of cutting the rod are considered, resulting in an optimal solution for maximizing profit.
