Box Stacking Problem

This is a C++ Program that Solves Box Stacking Problem using Dynamic Programming technique.

Problem Description

There are n cuboidal boxes. The dimensions of these boxes(length, breadth and height) are given. The objective is to stack the boxes to achieve maximum height. But you can place a box on top of another box only if its base dimensions are strictly lower than the other box. You can rotate the boxes. Also, you can use multiple instances of the same box.

Problem Solution

This problem is a variation of Longest increasing subsequence. The dimensions of the boxes are given. First, generate all the dimensions(by rotating). Then sort all these dimensions based upon the base (l*b). Now, simply apply LIS technique on these dimensions.

Expected Input and Output

Case-1:

 
n=3
 
dimensions(l,b,h)
box 1 - (1,2,3)
box 2 - (2,3,4)
box 3 - (3,4,5)
 
Expected result=15 
 
Stacking from top to bottom
1,2,3
2,3,4
3,4,5
4,5,3

Case-2:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

 
n=3
 
dimensions(l,b,h)
box 1 - (1,2,3)
box 2 - (2,3,4)
box 3 - (4,5,6)
 
Expected result=19
 
Stacking from top to bottom
1,2,3
2,3,4
3,4,2
4,5,6
5,6,4

Program/Source Code

Here is source code of the C++ Program to Solve Box Stacking Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<vector>
```
```
#include<algorithm>
```
```
using namespace std;
```
```
 
```

//this structure contains the variables for the dimensions of a box ie, length, breadth and height

```
struct box
```
```
{
```
```
    int l,b,h;
```
```
};
```
```
 
```

//comparison function used for sorting of all the boxes based on their base area

```
bool compare(box one, box two)
```
```
{
```
```
    return one.l*one.b < two.l*two.b;
```
```
}
```
```
 
```

int boxStacking(vector<box> boxes, int n)

```
{
```
```
    int i,j;
```
```
 
```
```
    //vector to store all the results
```
```
    vector<int> lis(3*n);
```
```
 
```

    //lis[i]=maximum attainable height by including box i at the bottom

```
 
```
```
    //initialization
```
```
    for(i=0;i<3*n;i++)
```
```
        lis[i]=boxes[i].h;
```
```
 
```

    //implementing linear increasing subsequence approach

```
    for(i=1;i<3*n;i++)
```
```
    {
```
```
        for(j=0;j<i;j++)
```
```
        {
```

            //if dimensions of box j are lesser than box i

            //box j can be placed on top of box i

            if(boxes[j].l<boxes[i].l && boxes[j].b<boxes[i].b)

```
            {
```

                if(lis[j]+boxes[i].h>lis[i])

                    lis[i]=lis[j]+boxes[i].h;

```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    int maxHeight=lis[0];
```
```
 
```

    //now, choose the one which gives the maximum height

```
    for(i=1;i<3*n;i++)
```
```
    {
```
```
        if(lis[i]>maxHeight)
```
```
            maxHeight=lis[i];
```
```
    }
```
```
 
```
```
    return maxHeight;
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int n;
```
```
    int l,b,h;
```
```
 
```

    cout<<"Enter the number of boxes"<<endl;

```
    cin>>n;
```
```
 
```
```
    //there are n boxes
```

    //but a box can be rotated and can further give more boxes

    //so, we will be storing dimensions of 3*n boxes by including the dimensions of rotated boxes as well

```
    vector<box> boxes(3*n);
```
```
 
```
```
    for(int i=0;i<3*n;i++)
```
```
    {
```

        cout<<"Enter the dimensions of box (length,breadth,height)  ";

```
        cin>>l>>b>>h;
```
```
        boxes[i].l=min(b,h);
```
```
        boxes[i].b=max(b,h);
```
```
        boxes[i].h=l;
```
```
 
```
```
        i++;
```
```
 
```
```
        boxes[i].l=min(l,h);
```
```
        boxes[i].b=max(l,h);
```
```
        boxes[i].h=b;
```
```
 
```
```
        i++;
```
```
 
```
```
        boxes[i].l=min(l,b);
```
```
        boxes[i].b=max(l,b);
```
```
        boxes[i].h=h;
```
```
 
```
```
    }
```
```
 
```

    //sort the boxes based on the base area (l*b)

    sort(boxes.begin(),boxes.end(),compare);

```
 
```

    cout<<"Longest achievable height by stacking the boxes is "<<endl;

```
    cout<<boxStacking(boxes,n);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value for number of boxes and dimensions of each box. Then, we sort the ordering of these boxes with respect to the base area of the box. We pass these values to the function boxStacking as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Get Free Certificate of Merit in Data Structure I Now!

Runtime Test Cases

 
Case-1:
$ g++ box_stacking.cpp
$ ./a.out
Enter the number of boxes
3
Enter the dimensions of box (length,breadth,height)  1 2 3
Enter the dimensions of box (length,breadth,height)  2 3 4
Enter the dimensions of box (length,breadth,height)  4 5 6
Longest achievable height by stacking the boxes is 
19

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

« Prev - Longest Increasing Subsequence using Dynamic Programming

» Next - Building Bridges – Dynamic Programming Solutions

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Recommended Articles: