# Box stacking problem

Tags: , , , ,

Consider, we have been given 3-Dimensional boxes. Each box has width, depth and height (wi, di, hi). Box stacking problem is to stack these boxes in such a way that we achieve maximum height. There is one condition that is attached to it: A box can be placed on top of another only if both it’s base dimensions width and depth are less than a box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.

With conditions in place, with given n boxes, we are actually, we are building a pyramid of boxes with maximum height.

This problem is closely related to longest increasing subsequence.

## Recurrence relation for box stacking problem

Solution involves understanding of rotation aspects of the boxes. To avoid this aspect affect our solution, we list down all rotations of boxes as individual boxes. Therefore, for each box there are three representations. For example, for a box with dimensions a,b,c such that a>b>c

```representation 1 : h=a, w=b, d=c>;
representation 2 : h=b, w=a, d=c;
representation 3 : h=c, w=a, d=b
```

Without losing generalization, we can avoid representation where wi < di. Now that we have three representations for each box, our input space increases to 3XN and the solution will be using these 3N boxes. There is another catch here. This solution works only when there are multiple instances of each box and we can use two different orientations of the same box while fetching maximum height.

### Finding the sort order

Another problem is these boxes which are given to us are not ordered in any form. However, to stack boxes, we need to consider them in some order. As height does not affect stacking order, we can ignore it. Now, we have to consider only two dimensions.

Let’s say, we order boxes on the base area in decreasing order. How does it work? Consider two boxes with different base areas. It is impossible for a box with a larger base area to be stacked on top of a box with a smaller base area. There are only two dimensions, so at least one must be larger than the corresponding dimension smaller base area box. Therefore, if a box within our sequence can’t be placed on top, no box with a greater area can be placed on top either.

Let H(i) be the height of the stack of boxes 1,2,3,4…i. Modeling recurrent relation for H(i), put box i on a box j such that wi < wj and di < dj and H(j) is maximum for all j less than i.

`H(i) = max(H(i), H(j) for all j < i such that wi < wj && di < dj ) + hi`

Finally, output will be the maximum of all H[i].

### Show me dynamic programming implementation

```#include <iostream>
#include <algorithm>
using namespace std;

typedef struct box {
int width;
int depth;
int height;
} Box;

bool boxComparator(Box b1, Box b2) {
return ( b1.depth * b1.width > b2.depth * b2.width );
}

int findMaxHeightBoxStack(Box boxes[], int n)
{
int H[n];
for(int i=0; i<n; i++){
H[i] = boxes[i].height;
}
for(int i=1; i<n; i++){
for( int j=i-1; j>=0; j--){
if(boxes[j].width > boxes[i].width
&& boxes[j].depth > boxes[i].depth
&& H[j] + boxes[i].height){
H[i] = H[j] + boxes[i].height;
}
}
}

int maxHeight = 0 ;
for(int i=0; i<n; i++){
if(maxHeight < H[i]){
maxHeight = H[i];
}
}
return maxHeight;
}

int boxStacking(Box boxes[], int n)
{

Box orientations[3*n]; //for rotations
int index = 0;
for(int i=0; i<n; i++){
orientations[index] = boxes[i]; // first one as such
index++;

orientations[index].height = boxes[i].width;
orientations[index].width = max( boxes[i].height, boxes[i].depth) ;
orientations[index].depth = min( boxes[i].height, boxes[i].depth);

index++;
orientations[index].height = boxes[i].depth;
orientations[index].width = max( boxes[i].height, boxes[i].width) ;
orientations[index].depth = min( boxes[i].height, boxes[i].width) ;
index++;
}
n = 3*n;

sort(orientations, orientations+n, boxComparator);
return findMaxHeightBoxStack( orientations, n);
}

// Driver program
int main()
{
Box boxes[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
int n = sizeof(boxes)/sizeof(boxes[0]);
cout << "Maximum height is " << boxStacking(boxes, n);
return 0;
}
```

Implementation is quite simple, we need one dimension array H[]. These boxes are already sorted by area in decreasing order.

The complexity of the algorithm to find maximum height is O(n2) and space complexity is O(n).

This problem can be extended by putting boxes with K dimensions instead of 3 dimensions. Then also, the approach would be the same only number of orientations will change.

Please share if there is something is wrong or missing. If you want to contribute to algorithms and me, please contact us, we would love to hear from you.

Reference: https://people.cs.clemson.edu/~bcdean/dp_practice/dp_5.swf