Dynamic Programming – Cutting Rods

This problems is presented in Introduction to Algorithms as an intro to Dynamic Programming.

Given a rod of length n inches and a table of prices pi for rod lengths: i = 1, 2, ... n, determine the maximum revenue rn obtainable by cutting up the rod to pieces and selling them.
The table looks like this :

A naive solution could be

```CUT-ROD(p, n) q = 0 for i = 1 to n q = max(q, p[i] + CUT-ROD(p, n - i)) return q ```

This solution has exponential asymptotic time.

So, we’re introduced to dynamic programing.

The method works as follows:

• We rearrange for each subproblem to be solved only once.
• If we need to refer to this subproblem’s solution again later, we can just look it up in a hash table or an array.

The modified version of the previous algorithm is:

``` CUT-ROD(p, n) // is solved before - use previous solutions if CUT-ROD(p, n) return s[n] q = 0 for i = 1 to n q = max(q, p[i] + CUT-ROD(p, n - i)) // store the new solution s[n] = q return q ```

There’s a top-down approach and a bottom-up approach:

The top-down approach recurses from larger problems to smaller subproblems until it reaches a pre-calculated subproblem. After that, it returns then combines the solutions of subproblems to solve the larger ones. The previous algorithm is top-down.

The bottom-up method, as you can tell from its name, solves all the required subproblems first then the larger ones. Both methods are O(n^2) but the bottom-up way has better constants.

To get a clear insight of what the difference is, see the following subproblem tree:

The subproblem graph for the rod-cutting problem with n = 4.The vertex labels give the sizes of the corresponding subproblems.

A directed edge (x, y) indicates that we need a solution to subproblem y when solving subproblem x.
To the left is the naive solution.To the right is the DP one.

Implemented below in C++
``` #include "iostream" #include "cstring" using namespace std;```

``` const int N = 1000; int p[11]; int r[N], s[N]; // initializer for prieces and optimal solutions void init() { memset(r, -1, N); r[0] = 0; p[0] = 0; p[1] = 1; p[2] = 5; p[3] = 8; p[4] = 9; p[5] = 10; p[6] = 17; p[7] = 17; p[8] = 20; p[9] = 24; p[10] = 30; } ```

```// naieve exponential solution int cutRod(int n) { int q = 0; for (int i = 1; i <= n; ++i) q = max(q, p[i] + cutRod(n - i)); return q; } // top-down solution int topDownCutRod(int n) { if (r[n] != -1) return r[n]; int q = 0; for (int i = 1; i <= n; ++i) q = max(q, p[i] + topDownCutRod(n - i)); return r[n] = q; } // bottom-up solution int buttomUpCutRod(int n) { if (r[n] != -1) return r[n]; for (int j = 1; j <= n; ++j) { int q = 0; for (int i = 1; i <= j; ++i) q = max(q, p[i] + r[j - i]); r[j] = q; } return r[n]; } // bottom-up solution that maintains not only the best price // but also the "required cut" for such solution the "required cut" // for such solution int extendedButtomUpCutRod(int n) { if (r[n] != -1) return r[n]; for (int j = 1; j <= n; ++j) { int q = 0; for (int i = 1; i <= j; ++i) if (q < p[i] + r[j - i]) { q = p[i] + r[j - i]; s[j] = i; } r[j] = q; } return r[n]; } // prins the extended method's output void printCutRodSoln(int n) { do cout << s[n] << " "; while ((n -= s[n]) > 0); } int main() { init(); int n; cin << n; cout << extendedButtomUpCutRod(n) << endl; printCutRodSoln(n); return 0; } ```
article from : http://gsourcecode.wordpress.com/2012/04/12/cutting-rods-introduction-to-dynamic-programming/