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.
- The top box should have less length and width than that of bottom box.
- 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 4th 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:
- Start i from index 1 and j from index 0.
- 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 2nd index = 5 x 3
Box at j = Box at 0th 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 2nd index = 5 x 3
Can go on top of, Box at j = Box at 1st 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 3rd index = 4 x 3
Can go on top of, Box at j = Box at 0th 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 3rd index = 4 x 3
Can go on top of, Box at j = Box at 1st index = 6 x 3. No.
Again increment j value and check:
Box at i = Box at 3rd index = 4 x 3
Can go on top of, Box at j = Box at 2nd 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 4th index = 5 x 2
Can go on top of, Box at j = Box at 0th 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 4th index = 5 x 2
Can go on top of, Box at j = Box at 1st 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 4th index = 5 x 2
Can go on top of, Box at j = Box at 2nd index = 5 x 3. No.
Now increment j value and check again.
Box at i = Box at 4th index = 5 x 2
Can go on top of, Box at j = Box at 2nd 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 5th index = 3 x 2
Can go on top of, Box at j = Box at 0th 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 5th index = 3 x 2
Can go on top of, Box at j = Box at 1st index = 6 x 3. No.
Now increment j value and check again.
Box at i = Box at 5th index = 3 x 2
Can go on top of, Box at j = Box at 2nd 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 5th index = 3 x 2
Can go on top of, Box at j = Box at 3rd 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 5th index = 3 x 2
Can go on top of, Box at j = Box at 4th 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
