Dynamic Programming: Box Stacking Problem

This is a classical DP problem.

In this tutorial we shall see how to solve box stacking problem. We shall solve it by DP approach.

Problem Statement:

You are given n number of boxes, and you need to place the boxes on top of each other such that you get the maximum height and by satisfying below property.

1. The top box should have less length and width than that of bottom box.
2. You are allowed to rotate the box in any way.

Let’s understand above question with help of a diagram,

In the image above, we have 2 boxes of dimension 5 x 5 x 5 i.e length, width and height. Second box of 4 x 3 x 2. According to the question, you need to stack the boxes which will return maximum height.

So first we shall place our larger box of 5 x 5 x 5. Then we shall place another box of 4 x 3 x 2. Then we shall rotate the box 2 and place it as 3 x 2 x 4.

So from the image above, we can see that we have stacked 3 boxes, along with satisfying the conditions. We cannot stack the 4^th box, because it will break our condition.

Hence the total height will be 4 + 2 + 5 = 11

So we shall solve this problem with help of DP along with longest increasing subsequence concept.

Consider 2 boxes of given dimensions:

Box 1 = { 2 x 3 x 5 }
Box 2 = { 4 x 3 x 6 }

Now, we shall rotate the boxes and list down al the possible rotations in such a way that the length is always greater than or equal to width.

In the above image, box 1 can be rotated in 3 ways, when the length is greater than it’s width.

Similarly box 2 can also be rotated in 3 ways where the length is greater than it’s width.

Why do we do this? It can be explained as below:

Now the next step is to sort them in decreasing order of base area.

Base area = l * w.

We sort like that because, we can stack box 2 upon box 1 if box 1 base area is greater than that of base 2.

So sorted order is

In the above image, we have 6 different boxes, hence our DP array will be 6 in size.

We shall take one more additional array to store which box can be stacked upon another.

Initially both array will be as below:

Our DP array is used to store maximum height, at the index 5, we will get our result.

Initially, when all the boxes are laid on the floor, the max height will be the height of the box. Hence dp array will be as below:

Now, as all the boxes are laid down, we can fill our result array with the same box index.

So from here we shall apply longest increasing subsequence concept.

The concept is as below:

1. Start i from index 1 and j from index 0.
2. Every time i and j meets, reset j value to 0 and increment index if i by 1

Initially “i” and j value will be as below

What we need to check here is, can the box at index i can go on top of box at index j.

Box at i = 6 x 3 and Box at j = 6 x 4.

Can 6 x 3 go on top of 6 x 4?

No, because the length is not smaller.

Hence move i to next location, and reset j value.

Now again check if the box at i can go on top of box at j.

Box at i = Box at 2^nd index = 5 x 3

Box at j = Box at 0^th  index = 6 x 4

Yes, it can go. Hence update the dp array with combined height i.e 2 + 3 = 5 and also indicate in our result array that box at index 2 is going on top of 0.

Now increment j value and again check.

Box at i = Box at 2^nd index = 5 x 3

Can go on top of, Box at j = Box at 1^st index = 6 x 3. No because width are same.

Hence, now reset j to 0 and i to 3 and check again.

Now can,

Box at i = Box at 3^rd index = 4 x 3

Can go on top of, Box at j = Box at 0^th index = 6 x 4. Yes.

Hence update the DP array with the height of both boxes. 6 + 3 = 9. And also result array to indicate box at index 3 can go on top of the box at index 0.

Now increment j value and check again

Box at i = Box at 3^rd index = 4 x 3

Can go on top of, Box at j = Box at 1^st index = 6 x 3. No.

Again increment j value and check:

Box at i = Box at 3^rd index = 4 x 3

Can go on top of, Box at j = Box at 2^nd index = 5 x 3. No.

Increment j value, as i and j index are same reset j to 0 and increment i value by 1.

Now check if

Box at i = Box at 4^th index = 5 x 2

Can go on top of, Box at j = Box at 0^th index = 6 x 4. Yes.

Update dp array with height 3 + 3 = 6 and result array to indicate 4 sits on top of 0.

Now increment j value and check again.

Box at i = Box at 4^th index = 5 x 2

Can go on top of, Box at j = Box at 1^st index = 6 x 3. Yes.

Update dp array with height 4 + 3 = 7 and result array to indicate 4 sits on top of 1.

Now increment j value and check again.

Box at i = Box at 4^th index = 5 x 2

Can go on top of, Box at j = Box at 2^nd index = 5 x 3. No.

Now increment j value and check again.

Box at i = Box at 4^th index = 5 x 2

Can go on top of, Box at j = Box at 2^nd index = 4 x 3. No.

Increment j value, as i and j index are same reset j to 0 and increment i value by 1.

Now check if

Box at i = Box at 5^th index = 3 x 2

Can go on top of, Box at j = Box at 0^th index = 6 x 4. Yes.

Update dp array with height 3 + 5 = 8 and result array to indicate 5 sits on top of 0.

Now increment j value and check again.

Box at i = Box at 5^th index = 3 x 2

Can go on top of, Box at j = Box at 1^st index = 6 x 3. No.

Now increment j value and check again.

Box at i = Box at 5^th index = 3 x 2

Can go on top of, Box at j = Box at 2^nd index = 5 x 3. yes.

Update dp array with height 2 + 3 = 5 and result array to indicate 5 sits on top of 2.

Now increment j value and check again.

Box at i = Box at 5^th index = 3 x 2

Can go on top of, Box at j = Box at 3^rd index = 4 x 3. Yes.

Update dp array with height 9 + 5 = 14 and result array to indicate 5 sits on top of 3 .

Now increment j value and check again.

Box at i = Box at 5^th index = 3 x 2

Can go on top of, Box at j = Box at 4^th index = 5 x 2. No.

Hence final result.

Now from our DP array we got to know that the max height is 14.

With the help of result array, we can get the box details.

So the box at index 5 will be on top.

3 x 2 x 5

Next in the index 5, there is index 3 box that will be below index 5 box as :

Box at index 5      3 x 2 x 5

Box at index 3      4 x 3 x 6

At index 3, we can get the box number 0.

Box at index 5      3 x 2 x 5

Box at index 3      4 x 3 x 6

Box at index 0      6 x 4 x 3

To calculate the height, add the first measurement of the 3 boxes. i.e 5 + 6 + 3 = 14

Hence the result.

Solution in C++

#include <iostream>
using namespace std;

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


// helper function
int compare (const void *a, const void * b) 
{
    return ( (*(Box *)b).depth * (*(Box *)b).width ) -
            ( (*(Box *)a).depth * (*(Box *)a).width );
}

int boxStackingHeight( Box boxDimensions[], int n ) 
{
    //Generate all 3 rotations of all boxes.
    Box rotation[3*n];
    int index = 0;
    for (int i = 0; i < n; i++) {
        // First Rotation
        rotation[index].height = boxDimensions[i].height;
        rotation[index].depth = max(boxDimensions[i].depth, boxDimensions[i].width);
        rotation[index].width = min(boxDimensions[i].depth, boxDimensions[i].width);
        index++;

        // Second rotation of box
        rotation[index].height = boxDimensions[i].width;
        rotation[index].depth = max(boxDimensions[i].height, boxDimensions[i].depth);
        rotation[index].width = min(boxDimensions[i].height, boxDimensions[i].depth);
        index++;

        // Third rotation of box
        rotation[index].height = boxDimensions[i].depth;
        rotation[index].depth = max(boxDimensions[i].height, boxDimensions[i].width);
        rotation[index].width = min(boxDimensions[i].height, boxDimensions[i].width);
        index++;
    }

    n = 3*n;

    // Sort the array 'rotation[]' in decreasing order of base area 
    qsort (rotation, n, sizeof(rotation[0]), compare);

    // Printing all rotations of the Box
    printf("All Rotations of the Boxes \n");
    for (int i = 0; i < n; i++ ) {
        printf("{%d x %d x %d}\n", rotation[i].height, rotation[i].width, rotation[i].depth);
    }

    // Initialize maxHeightOfStack values for all indexes
    // maxHeightOfStack[i] --> Maximum possible Stack Height with box i on top
    int maxHeightOfStack[n];
    for (int i = 0; i < n; i++ ) {
        maxHeightOfStack[i] = rotation[i].height;
    }

    // Compute optimized maxHeightOfStack values in bottom up manner
    for (int i = 1; i < n; i++ ){
        for (int j = 0; j < i; j++ ){
            if ( rotation[i].width < rotation[j].width &&
                    rotation[i].depth < rotation[j].depth &&
                    maxHeightOfStack[i] < maxHeightOfStack[j] + rotation[i].height) {
                maxHeightOfStack[i] = maxHeightOfStack[j] + rotation[i].height;
            }
        }
    }

    // Pick up the maximum height from the stack
    int max = -1;
    for ( int i = 0; i < n; i++ ) {
        if ( max < maxHeightOfStack[i] ) {
            max = maxHeightOfStack[i];
        }
    }
    return max;
}


int main() {

    Box box_dimensions[] = { {2, 3, 5}, {4, 3, 6} };

    int n = sizeof(box_dimensions)/sizeof(box_dimensions[0]);

    int maxHeight = boxStackingHeight(box_dimensions, n);

    printf("The maximum Possible Height of the Stack = %d\n", maxHeight);

    return 0;
}

Output:

All Rotations of the Boxes
{3 x 4 x 6}
{4 x 3 x 6}
{2 x 3 x 5}
{6 x 3 x 4}
{3 x 2 x 5}
{5 x 2 x 3}
The maximum Possible Height of the Stack = 14

List Of Tutorials available in this website: