Dynamic Programming | Set 13 (Cutting a Rod) | GeeksforGeeks
Given a rod of length n inches 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.
X. Top Down
http://blog.giovannibotta.net/2012/04/dynamic-programming-and-memoization.html
Dynamic programming algorithms can usually be written in a recursive fashion, i.e., with a top-down approach.
memoization is great because it allows writing code in a natural way, but it leaves us with a lot of overhead due to the call stack. The solution is to write the algorithm in a bottom-up fashion instead. This means solving the simplest sub-problems first and then using them to solve the higher level sub-problems in progressive order.
Going back to our Fibonacci sequence, this means computing the elements of the sequence one after the other starting from F0 = 0 and F1 = 1, F2 = F0+F1 and so on. The recursive program can be now written in iterative form, e.g., in a for loop. It's worth noting that the asymptotic running time is still O(n), but the time saved by reducing the call stack overhead will noticeably improve the constant factors, leading to a faster algorithm.
Given a rod of length n inches 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.
For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20
DP-O(N^2)
We can get the best price by making a cut at different
positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
We can get the best price by making a cut at different
positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
Let cutRoad(n) be the required (best possible price) value for a rod of lenght n. cutRod(n) can be written as following.
cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}
max_val = max(max_val, price[i] + cutRod(price, n-i-1));
int cutRod(int price[], int n){ if (n <= 0) return 0; int max_val = INT_MIN; // Recursively cut the rod in different pieces and compare different // configurations for (int i = 0; i<n; i++) max_val = max(max_val, price[i] + cutRod(price, n-i-1)); return max_val;}http://blog.giovannibotta.net/2012/04/dynamic-programming-and-memoization.html
Dynamic programming algorithms can usually be written in a recursive fashion, i.e., with a top-down approach.
memoization is great because it allows writing code in a natural way, but it leaves us with a lot of overhead due to the call stack. The solution is to write the algorithm in a bottom-up fashion instead. This means solving the simplest sub-problems first and then using them to solve the higher level sub-problems in progressive order.
Going back to our Fibonacci sequence, this means computing the elements of the sequence one after the other starting from F0 = 0 and F1 = 1, F2 = F0+F1 and so on. The recursive program can be now written in iterative form, e.g., in a for loop. It's worth noting that the asymptotic running time is still O(n), but the time saved by reducing the call stack overhead will noticeably improve the constant factors, leading to a faster algorithm.
public int cutRodMemoized(int[] p, int n) {
int r[] = new int[p.length + 1];
Arrays.fill(r, Integer.MIN_VALUE);
return cutRodMemoizedAux(p, n, r);
}
private int cutRodMemoizedAux(int[] p, int n, int[] r) {
if (r[n] >= 0)
return r[n];
int q = 0;
if (n != 0) {
q = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++)
q = Math.max(q, p[i - 1] + cutRodMemoizedAux(p, n - i, r));
}
r[n] = q;
return q;
} 