This post has already been read 4148 times!

**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/