Box Stacking Problem

Given a set of rectangular 3D boxes, create a stack of boxes which is as tall as possible. A box can be placed on top of another box if the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box. Multiple instances of the same box can be used such that a box can be rotated to use any side as its base.


 

For example, consider below boxes where each box has dimensions L x W x H

(4 x 2 x 5)
(3 x 1 x 6)
(3 x 2 x 1)
(6 x 3 x 8)

 
The rotations of the boxes are:

(4 x 2 x 5)
(5 x 4 x 2)
(5 x 2 x 4)

(3 x 1 x 6)
(6 x 3 x 1)
(6 x 1 x 3)

(3 x 2 x 1)
(3 x 1 x 2)
(2 x 1 x 3)

(6 x 3 x 8)
(8 x 6 x 3)
(8 x 3 x 6)

 
The maximum height possible is 22 which can be obtained by boxes in following order:

(3 x 1 x 6)
(4 x 2 x 5)
(6 x 3 x 8)
(8 x 6 x 3)

 

 
The idea is to use Dynamic Programming to solve this problem. We start by generating all rotations of each box. For simplicity, we can easily enforce the constraint that the width of a box is never more than the length. After generating all rotations, we sort the boxes in descending order of area and then apply the LIS algorithm to the get the maximum height. Let L(i) stores the maximum possible height when i'th box is on the top. Then, the recurrence is:

L(i) = height(i) + max(L(j) | j < i and block i can be put on top of block j)

 
Finally, the maximum height is the maximum value in L[]. The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

The maximum height is 22

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n) where n is the number of boxes.

 
Problem source: http://people.csail.mit.edu/bdean/6.046/dp/

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Joe
Guest

great

Charlie
Guest
Charlie

I think it is key to mention that multiple instances of the same box can be used.

Also, line 48 should be “x.length * x.width”, not “x.length * y.width”?