The box stacking problem is a variation of the Longest Increasing Subsequence problem. The statement is that we are given n types of rectangular boxes. They are represented in 3D space by 3 values: height, weight and length. We have to stack them one on top of each other, in order to obtain the maximum height possible for the stack. There is one rule to apply: the boxes in the stack must be stacked in such a way, that any box will have its base smaller than the box below. The box can be rotated on any axes so that any face can be the base, and we are allowed to use multiple instances of the same box.
// Box Stacking problem
#include <iostream>
using namespace std;
struct Box
{
int height;
int width;
int depth;
};
int minimumNumber (int x, int y)
{
return (x < y)? x : y;
}
int maximumNumber (int x, int y)
{
return (x > y)? x : y;
}
int compare (const void *a, const void * b)
{
return ( (*(Box *)b).depth * (*(Box *)b).width ) - ( (*(Box *)a).depth * (*(Box *)a).width );
}
int maxStackHeight( Box boxArray[], int numberOfBoxes )
{
int instancesOfBox = 3;
Box rotationBoxes[instancesOfBox * numberOfBoxes];
int index = 0;
for (int i = 0; i < numberOfBoxes; i++)
{
// Copy of the initial box
rotationBoxes[index].height = boxArray[i].height;
rotationBoxes[index].depth = maximumNumber(boxArray[i].depth, boxArray[i].width);
rotationBoxes[index].width = minimumNumber(boxArray[i].depth, boxArray[i].width);
index++;
// Rotation 1 of box
rotationBoxes[index].height = boxArray[i].width;
rotationBoxes[index].depth = maximumNumber(boxArray[i].height, boxArray[i].depth);
rotationBoxes[index].width = minimumNumber(boxArray[i].height, boxArray[i].depth);
index++;
// Rotation 2 of box
rotationBoxes[index].height = boxArray[i].depth;
rotationBoxes[index].depth = maximumNumber(boxArray[i].height, boxArray[i].width);
rotationBoxes[index].width = minimumNumber(boxArray[i].height, boxArray[i].width);
index++;
}
numberOfBoxes = instancesOfBox * numberOfBoxes;
// Sort the boxes in decreasing order of base
qsort (rotationBoxes, numberOfBoxes, sizeof(rotationBoxes[0]), compare);
int maxStackHeight[numberOfBoxes];
for (int i = 0; i < numberOfBoxes; i++ )
{
maxStackHeight[i] = rotationBoxes[i].height;
}
// Verify all the combinations
for (int i = 1; i < numberOfBoxes; i++ )
{
for (int j = 0; j < i; j++ )
{
if ( rotationBoxes[i].width < rotationBoxes[j].width &&
rotationBoxes[i].depth < rotationBoxes[j].depth &&
maxStackHeight[i] < maxStackHeight[j] + rotationBoxes[i].height)
{
maxStackHeight[i] = maxStackHeight[j] + rotationBoxes[i].height;
}
}
}
// Select the maximum height
int maximumNumber = -1;
for (int i = 0; i < numberOfBoxes; i++)
{
if (maximumNumber < maxStackHeight[i])
{
maximumNumber = maxStackHeight[i];
}
}
return maximumNumber;
}
int main()
{
Box boxArray[] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9 } };
int numberOfBoxes = sizeof(boxArray)/sizeof(boxArray[0]);
int maxHeightOfStack = maxStackHeight(boxArray, numberOfBoxes);
cout << "The maximum height of the stack is " << maxHeightOfStack << endl;
return 0;
}
The maximum height of the stack is 30.
Comments