Dynamic Programming – Box Stacking Problem

Objective: 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.

Source : http://people.csail.mit.edu/bdean/6.046/dp/ ,

Box Stacking 1


So we have n boxes. first thing we will concentrate about box rotations since we each rotation will create more possibilities for making stack, remember we have unlimited number of boxes.

Box Rotations:

Though we say that we can rotate a box but if you look closely we have one 3 unique possibilities which will have different base area.

Box Stacking - Rotations

So for each given box we will generate all the possibilities. Since we have unlimited boxes we will use all the boxes to make the stack of maximum height.

Now this problem has reduced to the variation of Longest Increasing Subsequence.

Now to create the stack of maximum height we need to place the box with max base area at the bottom and on top of that box with 2nd best base area and so on.

Sort the boxes in descending order based on the their base area. (I have solved this problem in java so i have  overridden the compareTo(). Click here to read more about how to sort java objects. )

Now we have all the boxes in sorted order. We will take one box at a time ( in descending order) . A box can be placed on another box only when the upper box is strictly larger than the lower box means width and depth of the upper box is greater than the lower box.

Let’s say

optHeight[i] =  Maximum stack height created by i boxes.  

For every box we have two options either it can be placed of one of the boxes if it is smaller than those boxes or start a new stack with that box. So we will be creating multiple stacks. At the end we will return the height of biggest stack.

Let’s see how the recursive equation will look like

Box Stacking - Recurrence Equation


import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class BoxStacking {
public int solve(int [][] x){
Box [] boxes = new Box[x.length*3];
for (int i = 0; i<x.length ; i++) {
int h = x[i][0];
int w = x[i][1];
int d = x[i][2];
boxes[i*3] = new Box(h,w,d); //normal dimension
boxes[i*3+1] = new Box(w,h,d); //first dimension
boxes[i*3+2] = new Box(d,h,w); //second dimension
//all options are created.
//to display all the possible boxes.
System.out.println("All possible combination of boxes after rotation");
for (int i = 0; i <boxes.length ; i++) {
System.out.println(boxes[i].height + " " + boxes[i].width + " " + boxes[i].depth);
int [] optHeight = new int [boxes.length+1];
//if there are no boxes then optimal height = 0
optHeight[0] =0;
for (int i = 1; i <optHeight.length ; i++) {
int maxHeightIndex = 0;
for (int j = i1; j >=0 ; j–) {
//first check if box can be placed
if(boxes[j].width>boxes[i1].width && boxes[j].depth>boxes[i1].depth){
maxHeightIndex = j+1;
optHeight[i]=optHeight[maxHeightIndex] + boxes[i1].height;
// System.out.println(Arrays.toString(optHeight));
return optHeight[optHeight.length1];
public static void main(String[] args) {
int [][] x = { {4, 7, 9},
{5, 8, 9},
{11, 20, 40},
{1, 2, 3} };
BoxStacking boxStacking = new BoxStacking();
System.out.println("Max height which can be obtained :" + boxStacking.solve(x));
class Box implements Comparable<Box>{
int height;
int width;
int depth;
public Box(int height, int width, int depth){
this.height = height;
this.width = width;
this.depth = depth;
public int compareTo(Box o) {
int area = o.depth*o.width;
int thisArea = this.depth*this.width;
return areathisArea;


All possible combination of boxes after rotation

11 20 40
20 11 40
40 11 20
5 8 9
4 7 9
8 5 9
9 5 8
7 4 9
9 4 7
1 2 3
2 1 3
3 1 2

Max height which can be obtained :78

1 thought on “Dynamic Programming – Box Stacking Problem”

Leave a Reply to Sid L Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.