Box stacking Problem

Reading time: 30 minutes | Coding time: 20 minutes

Algorithm

This problem can be seen as a variation of the dynamic programming problem LIS (longest increasing sequence). The steps to solve the problem are:

1. Compute the rotations of the given types of boxes.
2. Sort the boxes by decreasing order of area.
3. Find the longest increasing sequence of boxes.

Pseudocode

Pseudocode of the Box Stacking problem is as follows:

1. initialize new array of boxes of length n*3 which will store all three rotations of box.
2. sort the array in decreasing order of area of boxes
3. initialize new array maxHeight of length n*3 which will store the max height achivable by having box i at the top
4. now the problem is same as LIS with following optimal substructure property.
    maxHeight[i] = { Max ( maxHeight[j] ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i). If there is no such j then maxHeight[i] = height(i)
5. iterate through array maxHeight and return max element from it.

Complexity

• Time complexity: Θ(n2)
• Space complexity: Θ(n)

Implementation

Implementations of Box Stacking Problem is as follows:

• Java

import java.util.*;
import java.lang.*;
public class Solution {
	static class Box implements Comparable<Box>
    {
		int height, width, depth, area; 
		Box(int h, int w, int d)
        {
			this.height = h;
			this.width = w;
			this.depth = d;
			this.area = width * depth;
		}
		//helper function to sort boxes accroding to their area
		@Override
		public int compareTo(Box b) 
        {
			return b.area-this.area;
		}
	}
	static int getMaxHeight(int n, Box[] arr) 
    {
		//array to store all rotations of the boxes with original boxes
		Box []boxes = new Box[n*3];
		// generate all three rotations of the boxes
		for(int i = 0;i<n;i++) 
        {
			Box curr = arr[i];
			boxes[i*3] = new Box(curr.height,Math.min(curr.width, curr.depth),Math.max(curr.width, curr.depth));
			boxes[i*3 + 1] = new Box(curr.width, Math.min(curr.height, curr.depth), Math.max(curr.height, curr.depth));
			boxes[i*3 + 2] = new Box(curr.depth, Math.min(curr.height, curr.width), Math.max(curr.height, curr.width));
		}
		Arrays.sort(boxes);
		n *= 3;
		//initialize array to store the achievable max height by having box i at the top of the stack
		int maxHeight[] = new int[n];
		for(int i = 0;i<n;i++) maxHeight[i] = boxes[i].height;
		//iterate through all the boxes and update maxHeight using dp
		for(int i = 0;i<n;i++) 
        {
			Box curr = boxes[i];
			int val = 0;
			for(int j=0;j<i;j++) 
            {
				Box temp = boxes[j];
				if(temp.width > curr.width && temp.depth > curr.depth)
                    val = Math.max(val, maxHeight[j]);
			}
			maxHeight[i] += val;
		}
		//extract the max value from maxHeight and return
		int max = -1;
		for(int i = 0;i<n;i++) max = Math.max(max, maxHeight[i]);
		return max;
	}
	public static void main(String[] args) 
    {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		Box arr[] = new Box[n];
		for(int i = 0;i<n;i++) 
        {
			int h = s.nextInt();
			int w = s.nextInt();
			int d = s.nextInt();
			arr[i] = new Box(h,w,d);
		}
		System.out.println(getMaxHeight(n, arr));
	}
}

Example

Input:
4
4 6 7
1 2 3
4 5 6
10 12 32

Output:
60

You have an initial array of boxes as ${ {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} }$ where boxes are in format ${height, width, depth}$. Note that we are keeping the rotations of boxes in which $width<depth$, this is to simplify the algorithm i.e. in ${1,2,3}$ one of the rotations would be ${2,1,3}$ and other would be ${2,3,1}$ in this case we will keep the rotation ${2,1,3}$ only.

Now we can generate all the rotations of given boxes and the final array would be

{{4,6,7},
{6,4,7},
{7,4,6},
{1,2,3},
{2,1,3},
{3,1,2},
{4,5,6},
{5,4,6},
{6,4,5},
{10,12,32},
{12,10,32},
{32,10,12}}

Now we will sort the boxes in the decreasing order of the area. Remember, $area = width * depth$. The sorted array of boxes would be,

 {{10, 12, 32}
 {12, 10, 32}
 {32, 10, 12}
 {4, 6, 7}
 {4, 5, 6}
 {6, 4, 7}
 {5, 4, 6}
 {7, 4, 6}
 {6, 4, 5}
 {1, 2, 3}
 {2, 1, 3}
 {3, 1, 2}}

Now the algorithm would find the maximum height achieveable and the answer is $60$ for this example. The boxes which are selected are

$${{3, 1, 2}, {1, 2, 3}, {6, 4, 5}, {4, 5, 6}, {4, 6, 7}, {32, 10, 12}, {10, 12, 32}}$$

References/ Further reading

1. https://github.com/OpenGenus/cosmos/tree/master/code/dynamic_programming/src/box_stacking