QUESTION
Given a group of boxes, you are requested to arrange these boxes on top of each other to reach the maximum possible height. Note: a box cannot be placed on top of another box unless the area of its 2D base is smaller or equal of the 2D base of the lower box. It is allowed to rotated any box to use any two sides as its base.
For example, consider below 4 boxes where each box has the following dimensions
Input:
Box 1: (4,5,2), Box 2:(3,1,6), Box 3:(3,2,1),
Box 4:(6,8,3)
Output:
From bottom to top as follows:
Box 4 on the base (6,3) and height 8,
then Box 1 on the base (4,2) and height 5, then Box 2 on the base (1,3) and height 6, finally, on top Box 3 on the base (2,1) and height 3.
The total height is 22
[Explanation: as we can see that the first box in the bottom is the box # 4 with base 6x3 and height 8, then box # 1 with base 4x2 and height 5, and so on. This arrangement of boxes fulfils the constraint mentioned above: “the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box”. This solution also satisfies the tallest possible stack]