Box Stacking Problem using Dynamic Programming

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:

advertisement
advertisement
 
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.

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. //this structure contains the variables for the dimensions of a box ie, length, breadth and height
  7. struct box
  8. {
  9.     int l,b,h;
  10. };
  11.  
  12. //comparison function used for sorting of all the boxes based on their base area
  13. bool compare(box one, box two)
  14. {
  15.     return one.l*one.b < two.l*two.b;
  16. }
  17.  
  18. int boxStacking(vector<box> boxes, int n)
  19. {
  20.     int i,j;
  21.  
  22.     //vector to store all the results
  23.     vector<int> lis(3*n);
  24.  
  25.     //lis[i]=maximum attainable height by including box i at the bottom
  26.  
  27.     //initialization
  28.     for(i=0;i<3*n;i++)
  29.         lis[i]=boxes[i].h;
  30.  
  31.     //implementing linear increasing subsequence approach 
  32.     for(i=1;i<3*n;i++)
  33.     {
  34.         for(j=0;j<i;j++)
  35.         {
  36.             //if dimensions of box j are lesser than box i
  37.             //box j can be placed on top of box i
  38.             if(boxes[j].l<boxes[i].l && boxes[j].b<boxes[i].b)
  39.             {
  40.                 if(lis[j]+boxes[i].h>lis[i])
  41.                     lis[i]=lis[j]+boxes[i].h;
  42.             }
  43.         }
  44.     }
  45.  
  46.     int maxHeight=lis[0];
  47.  
  48.     //now, choose the one which gives the maximum height
  49.     for(i=1;i<3*n;i++)
  50.     {
  51.         if(lis[i]>maxHeight)
  52.             maxHeight=lis[i];
  53.     }
  54.  
  55.     return maxHeight;
  56. }
  57.  
  58. int main()
  59. {
  60.     int n;
  61.     int l,b,h;
  62.  
  63.     cout<<"Enter the number of boxes"<<endl;
  64.     cin>>n;
  65.  
  66.     //there are n boxes
  67.     //but a box can be rotated and can further give more boxes
  68.     //so, we will be storing dimensions of 3*n boxes by including the dimensions of rotated boxes as well
  69.     vector<box> boxes(3*n);
  70.  
  71.     for(int i=0;i<3*n;i++)
  72.     {
  73.         cout<<"Enter the dimensions of box (length,breadth,height)  ";
  74.         cin>>l>>b>>h;
  75.         boxes[i].l=min(b,h);
  76.         boxes[i].b=max(b,h);
  77.         boxes[i].h=l;
  78.  
  79.         i++;
  80.  
  81.         boxes[i].l=min(l,h);
  82.         boxes[i].b=max(l,h);
  83.         boxes[i].h=b;
  84.  
  85.         i++;
  86.  
  87.         boxes[i].l=min(l,b);
  88.         boxes[i].b=max(l,b);
  89.         boxes[i].h=h;
  90.  
  91.     }
  92.  
  93.     //sort the boxes based on the base area (l*b)
  94.     sort(boxes.begin(),boxes.end(),compare);
  95.  
  96.     cout<<"Longest achievable height by stacking the boxes is "<<endl;
  97.     cout<<boxStacking(boxes,n);
  98.  
  99.     cout<<endl;
  100.     return 0;
  101. }
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.

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.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.