Box Stacking Problem

By | October 9, 2015

Box Stacking Problem (using LIS).

Box Stacking Problem Statement:

Given N 3-D cuboid-al boxes  all with different Height Width and Depth.
We have to make a tower of maximum height using these boxes such that both the dimensions of the box stacked above are smaller than that of the box on which it is stacked.
We are allowed to use multiple instances of a given box ( in rotated form, at max 3).

Pre-requisite: Longest increasing subsequence.
This problem directly uses LIS and can be seen as an application.

Solution of Box Stacking Problem :

State of DP:

MSH[i]= Maximum possible Stack Height with box i at top of stack

Recursion for Box Stacking Problem :

MSH[i] = { Max ( MSH[i] )+ height[i]}

where j < i and width(j) > width(i) and depth(j) > depth(i).
If there is no such j then MSH[i] = height[i].

Algorithm:

  1. Store all the permutations possible for a single box, as its width or breadth can serve as the height too.
    Thus from one box, we can generate 3 boxes (considering depth <=width always). Now the size of the box array is 3N
  2. Sort the box array in DECREASING order of base area.
  3. Apply LIS using the recursion mentioned above and get the answer (max(MSH[i])).

Video Explanation:

click HERE for the video explanation.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure that stores the dimensions 
of the box */
struct box
{
   int h,w,d;
};

/*This compare function is used when we use the 
library function qsort().
Refer following link for help of qsort() and compare()
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */

int compare(const void *a, const void *b)
{
   return ((*(box *)b).d*(*(box *)b).w) - ((*(box *)a).d*(*(box *)a).w) ; 
}

int maxHeight(box a[],int n)
{
   /*This is the new array that would be */
   box r[3*n];
   int index=0,maxa;
   
   /*Generating permutations of the box,
   with assumption that depth<=width always*/
   
   for(int i=0;i<n;++i)
   {
      //original box copied
      r[index++]=a[i];
      
      //Box generated after 1st rotation
      r[index].h=a[i].d;	
      r[index].d=max(a[i].h,a[i].w);
      r[index++].w=min(a[i].h,a[i].w);
      
      //Box generated after 2nd rotation
      r[index].h=a[i].w;	
      r[index].d=max(a[i].h,a[i].d);
      r[index++].w=min(a[i].h,a[i].d);
   }	
      /*Now, we have 3N boxes*/
   n*=3;
   qsort(r,n,sizeof(box),compare);
   
   int hmax[n];
   
   for(int i=0;i<n;++i)
      hmax[i]=r[i].h;
      
   for(int i=1;i<n;++i)	
      for(int j=0;j<i;++j)
      /*In the if condition, we consider combinations of depth and width*/
         if((r[i].w<r[j].w && r[i].d<r[j].d 
            || r[j].d>r[i].w && r[j].w>r[i].d) 
            &&hmax[i]<hmax[j]+r[i].h ) //if conditions over
               hmax[i]=hmax[j]+r[i].h;
            
   /*Finding the maximum value*/
   maxa=hmax[0];
   for(int i=1;i<n;++i)
      if(maxa<hmax[i])
         maxa=hmax[i];
   return maxa;	
}

   /* Driver program to test above function */
int main()
{
   box arr[]={ {26 ,53 ,58},{97 ,93 ,23},{84 ,62 ,64},{33 ,83 ,27} };
  	int n = sizeof(arr)/sizeof(arr[0]);

   cout<<"The maximum possible height of stack is:\n";
   cout<<maxHeight(arr, n);
 
  return 0;
}

Output:

The maximum possible height of stack is:
278

In the above program, given input boxes are {26 ,53 ,58},{97 ,93 ,23},{84 ,62 ,64},{33 ,83 ,27}. Following are all rotations of the boxes in decreasing order of base area.

  62 X 64 X 84
  64 X 62 X 84
  84 X 62 X 64
  26 X 53 X 58
  27 X 33 X 83
  33 X 83 X 27
  93 X 23 X 97
  97 X 93 X 23
  53 X 26 X 58
  58 X 26 X 53
  83 X 27 X 33

Time Complexity: O(N2)
Auxiliary Space: O(N)

An application of this algorithm is the Spoj BABYTWR question. To understand how solution works, read the question and then refer to Spoj BABYTWR solution.