Introduction to 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)
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 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
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

6 comments

  1. […] – Let Me Count The Ways Posted on 28 April 2012 by MGhareeb32 A coin change Dynamic Programming problem. A buttom-up approach C […]

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

  3. Anonymous · · Reply

    Best explanation of all solutions.

  4. […] Source: Introduction to Dynamic Programming – Cutting Rods […]

  5. 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 :(

std::cout <<

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: