possible configuration of each box

Question

Problem: 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.

solution: I found the below solution at http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/

1) Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.

2) Sort the above generated 3n boxes in decreasing order of base area.

3) After sorting the boxes, the problem is same as LIS with following optimal substructure property. MSH(i) = Maximum possible Stack Height with box i at top of stack MSH(i) = { Max ( MSH(j) ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i). If there is no such j then MSH(i) = height(i)

4) To get overall maximum height, we return max(MSH(i)) where 0 < i < n

I think the solution is wrong as it just considers 3 rotation of all the boxes. To get the correct solution, it should generate 6 possible rotations. So, is the given solution incorrect, or is their any flaw in using 6 rotations?

Answer 1

No, it's sufficient to consider 3 "rotations" of each box, because the only possibilities to consider are which dimension to make the top and bottom (say) of the box perpendicular to, and there are only 3 of these. It might help to think of the 3 different possibilities for each box in that way, instead of as rotations.

The main point is that, after we have chosen which pair of sides of a box will be top and bottom (which we can do in 3 ways), we don't need to try the 2 different rotations of the box in the plane. We can always just go with (say) the rotation in which the box is wider than it is deep. How do we know that we won't miss any potentially good solutions by doing this? Because in any solution having a box that is deeper than it is wide, there must be a lowest such box b, and that box, plus everything above it, can be safely rotated 90 degrees. (We know it's safe to do this because it's the lowest such box in the solution -- so the box underneath it, if any, must itself be wider than it is deep, meaning that if we rotate b 90 degrees, it must still fit inside this lower box (I recommend verifying this algebraically).) We can keep transforming the lowest deeper-than-it-is-wide box in the solution until none remain, without ever changing the height of the solution. Since we can do this for any solution containing one or more deeper-than-it-is-wide boxes, it means that each one is exactly equivalent in quality to some solution in which every box is wider-than-it-is-deep, so we can totally ignore the former solutions.

Answer 2

Note this:

For simplicity, we consider depth as always smaller than or equal to width.

So, if the dimensions of a box are, for example, 3, 4 and 5, we consider the following three ways to put it on the stack:

• d=3, w=4, h=5
• d=3, w=5, h=4
• d=4, w=5, h=3

The other three rotations have depth larger than width, so we do not consider them:

• d=4, w=3, h=5
• d=5, w=3, h=4
• d=5, w=4, h=3

In order to see if one rectangle a x b can be fully covered by another one c x d, it is sufficient to turn them both so that a <= b and c <= d, and then check whether a <= c and b <= d. That's why it works.