Caută
  • oanaunciuleanu

Box stacking problem, Dynamic Programming in C++






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.

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now