The Box Pyramid Problem by Dynamic Programming

The Challenge

Consider the building of a pyramid from a collection of boxes. In order for a stack of boxes to look like a pyramid, each stacked box needs to have a smaller footprint than the box beneath it within the stack.

In other words, one box can only be placed on top of another if both its lenght and depth are less than than the box below it. But, the height is of no concern. A taller box can be stacked on top of a shorter one.

Given some collection of n boxes, each of which is specified by the length of its three dimensions, what is the tallest pyramid that can be built?

Step 1: Framing the Problem

Given a box, it can be placed in any of several orientations by rotation. In order to represent this as a DP problem, we want to enumerate the search space. So, in this case, we want to search orientations rather than boxes. So, we enumerate the orientations, in effect, considering each orientation to be a different box. To further simplify the representation, we'll orient the boxes so that the smaller of the two base dimensions is the width. In other words, given a box with dimensions x > y > z, we'll consider orientations:

But not orientations such as:

As presented to us, the boxes are not ordered -- imagine a room with boxes filling the floor. But, in order to consider how to stack the boxes, we'll need to search the space in some order. If we can't do this, it is going to be very hard to make one solution build upon a prior solution. And, remember, that is the name of the game for dynamic programming. So, we need to sort the boxes.

We know that the height of a box does not affect whether or not it can be stacked on top of another box, we might as well be stacking 2-dimensional cardboard squares. So we don't consider the height in the sorting. Instead we consider only the base dimensions.

We want an ordering that will enable us to consider the boxes "in order", deciding at each step whether or not to include a particular box, by considering the pyramid so far, rather than one that contains a box "later" that we could have used "earlier". Such a sorting does not exhibit the "optimal substructure" needed for dynamic programming.

So, we order the boxes in increasing order of the base area. Why does this work? Well, consider two boxes with different base areas. It is impossible for the box with the larger base area to be stacked on top of the box with the smaller base area -- there are only two dimensions, so at least one must be larger than the corresponding dimension of the box with the smaller base area. So, if some box within our sequence can't be placed on top -- no box with a greater area can be placed on top.

This ordering is not the only ordering that will work. For exmaple, we could have sorted the boxes by increasing width and broken ties by decreasing length. But, it is simple, easy to understand -- an imposed a valid ordering.

So, now what we have is fairly interesting. We have a sequence of boxes. Notice that word, "sequence". Interesting -- we are looking to stack smaller boxes on top of larger boxes. So, we are, in effect, looking to find a decreasing (non-contiguous) sequence.

No great surprise, this problem, properly framed, is similar to the classic "longest increasing subsequence problem" -- only it is decreasing and the boxes are weighted by their height rather than each element of the sequence being worth exactly one.

Step 2: The Recurrence Relation

Given the sequence of boxes, b1...bk, with corresponding heights, h1...hk, ordered as described above, the maximum height of a tower that can be built using boxes 1...i can be modeled as:

H(i) = max (H(i), H(j) + hj), for j=1...(i-1)

Step 3: The Table

Easy enough: The table is a 1D array, with the same number of elements as number of input boxes. Each ith element of the array records the maximum height of the pyramid that can be constructed using a subsequence of boxes from 1...i. Remember, the sequence is sorted as described above.

Step 4: Populate the Table

The table can be populated using nested for loops:

/*
 * h[x] = height of box x
 * c[x] = xth element fo the cost array, e.g. best soln up to x
 * b[x] = base area of box x
 *
 * ...sorted as described above
 */
for (int i=1; i <= n; i++) {
  c[i] = h[i]; //initialize each element to its own height -- seq size=1
  for (int j = 1; j<i; j++) {
    if (b[i] < b[j]) // compare areas to see if they can be stacked
      c[i] = max (c[i], c[j]+ h[j]);
  }
}

return max(c[1...n]);

Step 5: Annotation

What if we want to know the actual optimal solution, rather than just its height? Each time we replace an existing entry, we annote the entry with the new box. Each time we add a new box to the stack on top of an old box, ratehr than in place of an old box, we annote the table with a link to the entry for the optimal solution upon which we stacked.