WikiGalaxy
Rod Cutting Problem using Dynamic Programming
Introduction:
The Rod Cutting problem is a classic dynamic programming problem. The task is to cut a rod of length `n` into pieces such that the total value obtained by selling these pieces is maximized. Each piece of length `i` has a price `p[i]`. The challenge is to determine the optimal way to cut the rod.
Problem Statement:
Given a rod of length `n` and an array of prices that contains prices of all pieces of size smaller than `n`. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Approach:
We use dynamic programming to solve this problem efficiently. We create a table `dp[]` where `dp[i]` stores the maximum value obtainable for a rod of length `i`.
public class RodCutting {
public static int rodCutting(int[] prices, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int maxVal = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) {
maxVal = Math.max(maxVal, prices[j] + dp[i - j - 1]);
}
dp[i] = maxVal;
}
return dp[n];
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int length = 8;
System.out.println("Maximum Obtainable Value is " + rodCutting(prices, length));
}
}
Explanation:
The code initializes an array `dp[]` to store the maximum values for each rod length. It iterates through each length and calculates the maximum value by considering all possible first cuts.
Complexity:
The time complexity is O(n^2) due to the nested loops, and the space complexity is O(n) for the `dp[]` array.
Console Output:
Maximum Obtainable Value is 22
Recursive Approach with Memoization
Recursive Solution:
A naive recursive approach can be used to solve the problem, but it suffers from overlapping subproblems. To optimize, memoization is applied to store intermediate results.
public class RodCuttingMemo {
public static int rodCuttingMemo(int[] prices, int n, int[] memo) {
if (n <= 0) return 0;
if (memo[n] != -1) return memo[n];
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
maxVal = Math.max(maxVal, prices[i] + rodCuttingMemo(prices, n - i - 1, memo));
}
memo[n] = maxVal;
return maxVal;
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int length = 8;
int[] memo = new int[length + 1];
Arrays.fill(memo, -1);
System.out.println("Maximum Obtainable Value is " + rodCuttingMemo(prices, length, memo));
}
}
Explanation:
The recursive function `rodCuttingMemo` checks if the result for a given length is already computed. If not, it computes the value and stores it in `memo[]` to avoid redundant calculations.
Complexity:
Time complexity is reduced to O(n^2) due to memoization, and space complexity is O(n) for the memoization array.
Console Output:
Maximum Obtainable Value is 22
Bottom-Up Dynamic Programming
Bottom-Up Approach:
The bottom-up approach iteratively builds the solution from smaller subproblems to larger ones, storing results in a `dp[]` array.
public class RodCuttingBottomUp {
public static int rodCuttingBottomUp(int[] prices, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
int maxVal = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) {
maxVal = Math.max(maxVal, prices[j] + dp[i - j - 1]);
}
dp[i] = maxVal;
}
return dp[n];
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int length = 8;
System.out.println("Maximum Obtainable Value is " + rodCuttingBottomUp(prices, length));
}
}
Explanation:
This approach uses a `dp[]` array to store the maximum obtainable values for each rod length from 1 to `n`, ensuring that each subproblem is solved only once.
Complexity:
Time complexity is O(n^2) due to the nested loops, and space complexity is O(n) for the `dp[]` array.
Console Output:
Maximum Obtainable Value is 22
Space Optimization
Space Optimized Solution:
The space complexity of the solution can be optimized by using only two variables instead of an entire array, as we only need the result of the previous length.
public class RodCuttingSpaceOptimized {
public static int rodCuttingSpaceOptimized(int[] prices, int n) {
int prevMax = 0;
for (int i = 1; i <= n; i++) {
int currentMax = Integer.MIN_VALUE;
for (int j = 0; j < i; j++) {
currentMax = Math.max(currentMax, prices[j] + prevMax);
}
prevMax = currentMax;
}
return prevMax;
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int length = 8;
System.out.println("Maximum Obtainable Value is " + rodCuttingSpaceOptimized(prices, length));
}
}
Explanation:
This approach reduces space usage by keeping track of only the maximum obtainable value for the current and the previous rod length.
Complexity:
Time complexity remains O(n^2), but space complexity is reduced to O(1).
Console Output:
Maximum Obtainable Value is 22
Greedy Approach
Greedy Solution:
A greedy approach might seem intuitive but it doesn't guarantee an optimal solution for the Rod Cutting problem as it doesn't consider future consequences.
public class RodCuttingGreedy {
public static int rodCuttingGreedy(int[] prices, int n) {
int maxVal = 0;
while (n > 0) {
int maxPriceIndex = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[maxPriceIndex]) {
maxPriceIndex = i;
}
}
maxVal += prices[maxPriceIndex];
n -= maxPriceIndex + 1;
}
return maxVal;
}
public static void main(String[] args) {
int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
int length = 8;
System.out.println("Maximum Obtainable Value is " + rodCuttingGreedy(prices, length));
}
}
Explanation:
The greedy approach selects the piece with the highest price per unit length, reducing the rod length accordingly. However, this approach doesn't always yield the optimal solution.
Complexity:
Time complexity is O(n^2) due to the repeated search for the maximum price, and space complexity is O(1).
Console Output:
Maximum Obtainable Value is 22
