Problem

Given a set of rectangular 3D boxes, each with height, width and depth. Find the maximum height of the stack created from them

  • The lower box must have area larger than the higher box
  • A box can be rotated to any side
  • Can use multiple instances of the same box

Dynamic programming approach

  • Max height of stack at i = max height of stack at j + height of box i with i > j

  • Each box has 3 instances to try as it can be rotated to any side

Implementation


References