ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Dynamic Programming: Box Stacking Problem

prodevelopertutorial March 29, 2020

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,

 

Box Stacking Problem

 

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.

 

Box Stacking Problem

 

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.

 

Box Stacking Problem

 

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

Box Stacking Problem

 

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:

Box Stacking Problem

 

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:

 

Box Stacking Problem

 

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

Box Stacking Problem

 

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

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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.

Box Stacking Problem

 

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 .

 

Box Stacking Problem

 

 

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

 

 

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io