Box stacking problem – Dynamic programming

Box stacking problem

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 which 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 box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.

Box stacking problem

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 we have 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 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 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 base area in decreasing order. How does it work? Consider two boxes with different base areas. It is impossible for a box with larger base area to be stacked on top of a box with smaller base area. There are only two dimensions, so at least one must be larger than 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 height of stack of boxes 1,2,3,4…i. Modeling recurrent relation for H(i), we want to 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 max of all H[i].

Box stacking problem using dynamic programming implementation

Implementation is quite simple, we need one dimension array H[]. Each element H[i] represents H[i] using boxes from i to i. These boxes are already sorted by area in decreasing order.

#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()
{
    //Job jobs[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}};
    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;
}

Complexity of algorithm to find maximum height in box stacking problem 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, 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.

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