algorithm - Box stacking problem

Question

I found this famous dp problem in many places, but I can not figure out how to solve.

You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

This problem seems too complicated for me to figure out the steps. As it is 3D, I get three sequence of height, width and depth. But as it is possible to exchange 3 dimension the problem becomes more complicated for me. So please someone explain the steps to solve the problem when there is no swapping and then how to do it when swapping. I became tired about the problem. So please, please someone explain the solution easy way.

Answer 1

I think you can solve this using the dynamic programming longest increasing subsequence algorithm: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Accounting for the rotations is easy enough: for every tower all you have to check is what happens if you use its height as the length of the base and its width as the height and what happens if you use it in the natural way. For example:

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

Becomes something like (yeah, I know it looks nothing like it should, just follow the notations):

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

So for each block you actually have 3 blocks representing its possible rotations. Adjust your blocks array according to this, then sort by decreasing base area and just apply the DP LIS algorithm to the get the maximum height.

The adapted recurrence is: D[i] = maximum height we can obtain if the last tower must be i.

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

See a video explaning this here: http://people.csail.mit.edu/bdean/6.046/dp/