You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
The Box Stacking problem is a variation of LIS problem. We need to build a maximum height stack.
Following are the key points to note in the problem statement:
- A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.
- We can rotate boxes. For example, if there is a box with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities, {1x2x3}, {2x1x3} and {3x1x2}.
- We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.
Following is the solution based on DP solution of LIS problem.
- Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.
- Sort the above generated 3n boxes in decreasing order of base area.
- After sorting the boxes, the problem is same as LIS with following optimal substructure property.
MSH(i) = Maximum possible Stack Height with box i at top of stack
MSH(i) = { Max ( MSH(j) ) + 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) - To get overall maximum height, we return max(MSH(i)) where 0 < i < n
Following is C++ implementation of the above solution.
[pastacode lang=”cpp” manual=”%2F*%20Dynamic%20Programming%20implementation%20of%20Box%20Stacking%20problem%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Representation%20of%20a%20box%20*%2F%0Astruct%20Box%0A%7B%0A%20%20%2F%2F%20h%20–%3E%20height%2C%20w%20–%3E%20width%2C%20d%20–%3E%20depth%0A%20%20int%20h%2C%20w%2C%20d%3B%20%20%2F%2F%20for%20simplicity%20of%20solution%2C%20always%20keep%20w%20%3C%3D%20d%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20get%20minimum%20of%20two%20intgers%0Aint%20min%20(int%20x%2C%20int%20y)%0A%7B%20return%20(x%20%3C%20y)%3F%20x%20%3A%20y%3B%20%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20get%20maximum%20of%20two%20intgers%0Aint%20max%20(int%20x%2C%20int%20y)%0A%7B%20return%20(x%20%3E%20y)%3F%20x%20%3A%20y%3B%20%7D%0A%20%0A%2F*%20Following%20function%20is%20needed%20for%20library%20function%20qsort().%20We%0A%20%20%20use%20qsort()%20to%20sort%20boxes%20in%20decreasing%20order%20of%20base%20area.%20%0A%20%20%20Refer%20following%20link%20for%20help%20of%20qsort()%20and%20compare()%0A%20%20%20http%3A%2F%2Fwww.cplusplus.com%2Freference%2Fclibrary%2Fcstdlib%2Fqsort%2F%20*%2F%0Aint%20compare%20(const%20void%20*a%2C%20const%20void%20*%20b)%0A%7B%0A%20%20%20%20return%20(%20(*(Box%20*)b).d%20*%20(*(Box%20*)b).w%20)%20-%0A%20%20%20%20%20%20%20%20%20%20%20(%20(*(Box%20*)a).d%20*%20(*(Box%20*)a).w%20)%3B%0A%7D%0A%20%0A%2F*%20Returns%20the%20height%20of%20the%20tallest%20stack%20that%20can%20be%0A%20%20%20formed%20with%20give%20type%20of%20boxes%20*%2F%0Aint%20maxStackHeight(%20Box%20arr%5B%5D%2C%20int%20n%20)%0A%7B%0A%20%20%20%2F*%20Create%20an%20array%20of%20all%20rotations%20of%20given%20boxes%0A%20%20%20%20%20%20For%20example%2C%20for%20a%20box%20%7B1%2C%202%2C%203%7D%2C%20we%20consider%20three%0A%20%20%20%20%20%20instances%7B%7B1%2C%202%2C%203%7D%2C%20%7B2%2C%201%2C%203%7D%2C%20%7B3%2C%201%2C%202%7D%7D%20*%2F%0A%20%20%20Box%20rot%5B3*n%5D%3B%0A%20%20%20int%20index%20%3D%200%3B%0A%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%20Copy%20the%20original%20box%0A%20%20%20%20%20%20rot%5Bindex%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20index%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20First%20rotation%20of%20box%0A%20%20%20%20%20%20rot%5Bindex%5D.h%20%3D%20arr%5Bi%5D.w%3B%0A%20%20%20%20%20%20rot%5Bindex%5D.d%20%3D%20max(arr%5Bi%5D.h%2C%20arr%5Bi%5D.d)%3B%0A%20%20%20%20%20%20rot%5Bindex%5D.w%20%3D%20min(arr%5Bi%5D.h%2C%20arr%5Bi%5D.d)%3B%0A%20%20%20%20%20%20index%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%2F%2F%20Second%20rotation%20of%20box%0A%20%20%20%20%20%20rot%5Bindex%5D.h%20%3D%20arr%5Bi%5D.d%3B%0A%20%20%20%20%20%20rot%5Bindex%5D.d%20%3D%20max(arr%5Bi%5D.h%2C%20arr%5Bi%5D.w)%3B%0A%20%20%20%20%20%20rot%5Bindex%5D.w%20%3D%20min(arr%5Bi%5D.h%2C%20arr%5Bi%5D.w)%3B%0A%20%20%20%20%20%20index%2B%2B%3B%0A%20%20%20%7D%0A%20%0A%20%20%20%2F%2F%20Now%20the%20number%20of%20boxes%20is%203n%0A%20%20%20n%20%3D%203*n%3B%0A%20%0A%20%20%20%2F*%20Sort%20the%20array%20’rot%5B%5D’%20in%20decreasing%20order%2C%20using%20library%0A%20%20%20%20%20%20function%20for%20quick%20sort%20*%2F%0A%20%20%20qsort%20(rot%2C%20n%2C%20sizeof(rot%5B0%5D)%2C%20compare)%3B%0A%20%0A%20%20%20%2F%2F%20Uncomment%20following%20two%20lines%20to%20print%20all%20rotations%0A%20%20%20%2F%2F%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B%20)%0A%20%20%20%2F%2F%20%20%20%20printf(%22%25d%20x%20%25d%20x%20%25d%5Cn%22%2C%20rot%5Bi%5D.h%2C%20rot%5Bi%5D.w%2C%20rot%5Bi%5D.d)%3B%0A%20%0A%20%20%20%2F*%20Initialize%20msh%20values%20for%20all%20indexes%20%0A%20%20%20%20%20%20msh%5Bi%5D%20–%3E%20Maximum%20possible%20Stack%20Height%20with%20box%20i%20on%20top%20*%2F%0A%20%20%20int%20msh%5Bn%5D%3B%0A%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B%20)%0A%20%20%20%20%20%20msh%5Bi%5D%20%3D%20rot%5Bi%5D.h%3B%0A%20%0A%20%20%20%2F*%20Compute%20optimized%20msh%20values%20in%20bottom%20up%20manner%20*%2F%0A%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%3B%20i%2B%2B%20)%0A%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20i%3B%20j%2B%2B%20)%0A%20%20%20%20%20%20%20%20%20if%20(%20rot%5Bi%5D.w%20%3C%20rot%5Bj%5D.w%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20rot%5Bi%5D.d%20%3C%20rot%5Bj%5D.d%20%26%26%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20msh%5Bi%5D%20%3C%20msh%5Bj%5D%20%2B%20rot%5Bi%5D.h%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20msh%5Bi%5D%20%3D%20msh%5Bj%5D%20%2B%20rot%5Bi%5D.h%3B%0A%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%0A%20%20%20%2F*%20Pick%20maximum%20of%20all%20msh%20values%20*%2F%0A%20%20%20int%20max%20%3D%20-1%3B%0A%20%20%20for%20(%20int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B%20)%0A%20%20%20%20%20%20if%20(%20max%20%3C%20msh%5Bi%5D%20)%0A%20%20%20%20%20%20%20%20%20max%20%3D%20msh%5Bi%5D%3B%0A%20%0A%20%20%20return%20max%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20Box%20arr%5B%5D%20%3D%20%7B%20%7B4%2C%206%2C%207%7D%2C%20%7B1%2C%202%2C%203%7D%2C%20%7B4%2C%205%2C%206%7D%2C%20%7B10%2C%2012%2C%2032%7D%20%7D%3B%0A%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%0A%20%20printf(%22The%20maximum%20possible%20height%20of%20stack%20is%20%25d%5Cn%22%2C%0A%20%20%20%20%20%20%20%20%20maxStackHeight%20(arr%2C%20n)%20)%3B%0A%20%0A%20%20return%200%3B%0A%7D” message=”C++” highlight=”” provider=”manual”/]Output :
The maximum possible height of stack is 60
In the above program, given input boxes are {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}. Following are all rotations of the boxes in decreasing order of base area.
10 x 12 x 32 12 x 10 x 32 32 x 10 x 12 4 x 6 x 7 4 x 5 x 6 6 x 4 x 7 5 x 4 x 6 7 x 4 x 6 6 x 4 x 5 1 x 2 x 3 2 x 1 x 3 3 x 1 x 2
The height 60 is obtained by boxes { {3, 1, 2}, {1, 2, 3}, {6, 4, 5}, {4, 5, 6}, {4, 6, 7}, {32, 10, 12}, {10, 12, 32}}
Time Complexity: O(n^2)
Auxiliary Space: O(n)