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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a box (L x W x H) struct Box { // enforce constraint: width is never more than length int length, width, height; }; // Function to generate rotations of all the boxes vector<Box> createAllRotations(const vector<Box> &boxes) { // stores all rotations of each box vector<Box> rotations; // do for each box for (const Box &box: boxes) { // push the original box: {L x W x H} rotations.push_back(box); // push the first rotation: {max(L, H) x min(L, H) x W} rotations.push_back({ max(box.length, box.height), min(box.length, box.height), box.width }); // push the second rotation: {max(W, H) x min(W, H) x L} rotations.push_back({ max(box.width, box.height), min(box.width, box.height), box.length }); } return rotations; } // Create a stack of boxes which is as tall as possible int maxHeight(vector<Box> const& boxes) { // generate rotations of each box vector<Box> rotations = createAllRotations(boxes); // sort the boxes in descending order of base area(L x W) sort(rotations.begin(), rotations.end(), [](const Box &x, const Box &y) { return x.length * x.width > y.length * y.width; }); // max_height[i] stores the max possible height when i'th box is on the top vector<int> max_height(rotations.size()); // fill max_height[] in bottom-up manner for (int i = 0; i < rotations.size(); i++) { for (int j = 0; j < i; j++) { // dimentions of the lower box are each strictly larger than those // of the higher box if (rotations[i].length < rotations[j].length && rotations[i].width < rotations[j].width) { max_height[i] = max(max_height[i], max_height[j]); } } max_height[i] += rotations[i].height; } // return the maximum value in max_height[] return *max_element(max_height.begin(), max_height.end()); } // main function int main() { // input boxes vector<Box> boxes { { 4, 2, 5 }, { 3, 1, 6 }, { 3, 2, 1 }, { 6, 3, 8 } }; cout << "The maximum height is " << maxHeight(boxes); return 0; } |

`Output:`

The maximum height is 22

The time complexity of above solution is O(n^{2}) 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 our online compiler to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

great

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”?

Thanks a lot for bringing this typo to our notice. The article is updated.