Rod cutting by dynamic programming

A typical problem that suits well to show how dynamic programming works. We have a rod sized up to, let's say, 10. We can freely cut it in pieces (integer sized) to sell them at the best price. Given a price table, find out the way to get the most from it.

Here is a C++11 test case for GoogleTest that should clarify the requirements:

typedef std::vector<int> Vector;

unsigned cutRod(const Vector& price, unsigned size);

TEST(CutRod, Simple)
{
  Vector price { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

  ASSERT_EQ(30, cutRod(price, 10));
  ASSERT_EQ(25, cutRod(price, 9));
  ASSERT_EQ(18, cutRod(price, 7));
  ASSERT_EQ(10, cutRod(price, 4));
}

Given that price list, we see immediately that if we have in input a rod sized up to 3, the best strategy is selling it in a single piece.
But if we have a rod sized four, selling it untouched we'll get 9. Better if we split it in two rodes both sized two, that give us 5 + 5 = 10.
Similarly, a rod sized 7 is priced 17. If we split it in two parts sized 6 and 1, we'll get 17 + 1 = 18.

Brute force

We may think to apply a recursive approach to this problem to check all the possible cut combinations we can think of. It is very easy to write the relative code, but can't we expect it to scale well:

unsigned cutRod(const Vector& price, unsigned size)
{
  unsigned result = 0;
  for(unsigned i = 0; i < size; ++i)
    result = std::max(result, price[i] + cutRod(price, size - (i+1)));

  return result;
}

It is just a matter of recursively calling our function reducing each time the size of the rod we are considering. We compare any time the partial result with the one we have previously stored, keeping just the best one.

Top-down dynamic programming

One obvious problem in the previous solution is that we solve again and again the same sub-problems. We could save lot of running time storing them in a buffer. This simple but effective idea is the basic of the dynamic programming technique.

In this context, the bargain of using space to avoid spending time repeating the same task to get a partial result is called memoization (as keeping a memo).

Here is a possible top-down implementation, very close to the naive version seen above:

unsigned cutRod(const Vector& price, unsigned size)
{
  Vector memo(size + 1, -1);
  memo[0] = 0;

  return memoCutRod(price, size, memo);
}

Here cutRod() just creates a memo vector that would store the values for each sub-problem, as soon as we get its result. Then it would start the recursion calling a support function.

Notice that the memo buffer has one element more than the price list. This is for storing also the value of the dummy cut sized zero. It is not a strict necessity, since we know that it won't cost anything, but it would help to make our code cleaner.

unsigned memoCutRod(const Vector& price, unsigned size, Vector& memo)
{
  if(memo[size] >= 0) // 1
    return memo[size];

  unsigned result = 0; // 2
  for(unsigned i = 0; i < size; ++i)
    result = std::max(result, price[i] + memoCutRod(price, size - (i+1), memo));

  return memo[size] = result; // 3
}

1. If the realtive memo buffer is not negative, we have already calculated it. Job already done.
2. Otherwise we calculate the best price as seen before.
3. And we set a memo before returning it.

Bottom-up approach

Again dynamic programming, still using memoization as we have just seen, but starting from the bottom of the problem and crawling up to its top. In this case the implementation is even simpler, and avoid us the pain and the cost of recursion:

unsigned cutRod(const Vector& price, unsigned size)
{
  Vector memo(size + 1); // 1
  for(unsigned i = 1; i <= size; ++i) // 2
  {
    int value = -1; // 3
    for(unsigned j = 0; j < i; ++j) // 4
      value = std::max(value, price[j] + memo[i-j-1]);
    memo[i] = value;
  }

  return memo.back(); // 5
}

1. As in the top-down approach, we get an extra element in the memo vector, just to keep simpler the code. But this time we don't need to initialize it to a "bad" values, because we are setting it up iteratively starting from the beginning.
2. First element in memo is already set to its expected value (that is, zero) as courtesy of the vector constructor. We need to calculate all the other elements, up to the rightmost one.
3. Initialize the current memo value to less than the minimum acceptable value (meaning, less than zero).
4. Basically it is the same loop we have seen in the previous implementations, but here we explicitly go for the smaller element first.
5. End of the story, the answer is stored in the rightmost memo element.

Check on github for full C++11 code.