This post has already been read 3023 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 :
screenshot-at-2012-04-12-165850

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:
screenshot-at-2012-04-14-164607-e1334415808999

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/

Comments are closed.

Post Navigation