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 `p`

for rod lengths: _{i}`i = 1, 2, ... n`

, determine the maximum revenue `r`

obtainable by cutting up the rod to pieces and selling them._{n}

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)if CUT-ROD(p, n) is solved before // use previous solutions return s[n] q = 0 for i = 1 to n q = max(q, p[i] +CUT-ROD(p, n - i)) s[n] = q // store the new solution 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`but the bottom-up way has better constants.`

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

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 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; }

Advertisements

why the const N should be 1000 ?

Tried to change the N and increasing P[r] didnt work if later cin < n are bigger than 40 :(

LikeLike

Best explanation of all solutions.

LikeLike

Nice explanation. I was looking for help for UVA – 10003 and found it. Carry on!

LikeLike