This is a C++ Program that Solves Box Stacking Problem using Dynamic Programming technique.
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.
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.
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:
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
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;
}
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.
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.
- 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
- Apply for Data Structure Internship
- Practice Computer Science MCQs
- Buy Data Structure Books
- Buy Computer Science Books
- Apply for Computer Science Internship