Box Stacking

Problem:  You are given a set of boxes {b1,……,bn}. Each box bj has an associated width wj , height hj and depth dj . Give an algorithm for creating the highest possible stack of boxes with the constraint that if box bj is stacked on box bi, the 2D base of bi must be larger in both dimensions than the base of bj . You can of course, rotate the boxes to decide which face is the base, but you can use each box only once.
For example, given two boxes with h1 = 5;w1 = 5; d1 = 1 and h2 = 4;w2 = 5; h2 = 2, you should orient box 1 so that it has a base of 5x5 and a height of 1 and stack box 2 on top of it oriented so that it has a height of 5 for a total stack height of 6.

Solution:

Recursion: Memorize over H(j,R), the tallest stack of boxes with j on top with rotation R.

Running Time: The size of H is O(n |R_j|) where R is the number of possible rotations for a box.For our purposes, |R| = 3 (since we only care about which dimension we designate as the \height") so |H| = O(n). Filling in each element of H is also O(n) for a total running time of O(n²).

Code:

   1: public static int stackHeight(ArrayList<Box> boxes) {
   2:         if (boxes == null) {
   3:             return 0;
   4:         }
   5:         int h = 0;
   6:         for (Box b : boxes) {
   7:             h += b.height;
   8:         }
   9:         return h;
  10:     }
  11:     
  12:     public static ArrayList<Box> createStackR(Box[] boxes, Box bottom) {
  13:         int max_height = 0;
  14:         ArrayList<Box> max_stack = null;
  15:         for (int i = 0; i < boxes.length; i++) {
  16:             if (boxes[i].canBeAbove(bottom)) {
  17:                 ArrayList<Box> new_stack = createStackR(boxes, boxes[i]);
  18:                 int new_height = stackHeight(new_stack);
  19:                 if (new_height > max_height) {
  20:                     max_stack = new_stack;
  21:                     max_height = new_height;
  22:                 }
  23:             }
  24:         }
  25:         
  26:         if (max_stack == null) {
  27:             max_stack = new ArrayList<Box>();
  28:         }
  29:         if (bottom != null) {
  30:             max_stack.add(0, bottom);
  31:         }
  32:         
  33:         return max_stack;
  34:     }
  35:     
  36:     public static ArrayList<Box> createStackDP(Box[] boxes, Box bottom, HashMap<Box, ArrayList<Box>> stack_map) {
  37:         if (bottom != null && stack_map.containsKey(bottom)) {
  38:             return stack_map.get(bottom);
  39:         }
  40:         
  41:         int max_height = 0;
  42:         ArrayList<Box> max_stack = null;
  43:         for (int i = 0; i < boxes.length; i++) {
  44:             if (boxes[i].canBeAbove(bottom)) {
  45:                 ArrayList<Box> new_stack = createStackDP(boxes, boxes[i], stack_map);
  46:                 int new_height = stackHeight(new_stack);
  47:                 if (new_height > max_height) {
  48:                     max_stack = new_stack;
  49:                     max_height = new_height;
  50:                 }
  51:             }
  52:         }        
  53:         
  54:         if (max_stack == null) {
  55:             max_stack = new ArrayList<Box>();
  56:         }
  57:         if (bottom != null) {
  58:             max_stack.add(0, bottom);
  59:         }
  60:         stack_map.put(bottom, max_stack);
  61:         
  62:         return (ArrayList<Box>)max_stack.clone();
  63:     }
  64:         
  65:     
  66:     public static void main(String[] args) {
  67:         Box[] boxes = { new Box(1, 7, 4), new Box(2, 6, 9), new Box(4, 9, 6), new Box(10, 12, 8),
  68:                         new Box(6, 2, 5), new Box(3, 8, 5), new Box(5, 7, 7), new Box(2, 10, 16), new Box(12, 15, 9)};
  69:  
  70:         //ArrayList<Box> stack = createStackDP(boxes, null, new HashMap<Box, ArrayList<Box>>());
  71:         ArrayList<Box> stack = createStackR(boxes, null);        
  72:         for (int i = stack.size() - 1; i >= 0; i--) {
  73:             Box b = stack.get(i);
  74:             System.out.println(b.toString());
  75:         }
  76:     }
  77:  
  78: public class Box {
  79:     public int width;
  80:     public int height;
  81:     public int depth;
  82:     public Box(int w, int h, int d) {
  83:         width = w;
  84:         height = h;
  85:         depth = d;
  86:     }
  87:     
  88:     public boolean canBeUnder(Box b) {
  89:         if (width > b.width && height > b.height && depth > b.depth) {
  90:             return true;
  91:         }
  92:         return false;
  93:     }
  94:     
  95:     public boolean canBeAbove(Box b) {
  96:         if (b == null) {
  97:             return true;
  98:         }
  99:         if (width < b.width && height < b.height && depth < b.depth) {
 100:             return true;
 101:         }
 102:         return false;        
 103:     }
 104:     
 105:     public String toString() {
 106:         return "Box(" + width + "," + height + "," + depth + ")";
 107:     }
 108: }