# HelloKoding

Practical coding guides

# Box Stacking Problem

In this article, you will learn to analyze and resolve the Box stacking problem by using Dynamic programming algorithm

## Problem

• Given a set of rectangular 3D boxes, each with height, width, and depth
• Write an algorithm to find the maximum height of the stack created from them
• The lower box must have an area larger than the higher box

A box can be rotated to any side

You 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

DP_BoxStacking.java

``````package com.hellokoding.algorithm;

import java.util.Arrays;
import java.util.Comparator;

public class DP_BoxStacking {
static class Box {
int height;
int width;
int depth;
int area;

Box(int height, int width, int depth) {
this.height = height;
this.width = width;
this.depth = depth;
this.area = this.width * this.depth;
}
}

static int findMaxHeight(Box[] arr, int N) {
Box[] boxes = new Box[N*3];

for (int i = 0; i < N; i++) {
Box current = arr[i];
boxes[i*3] = new Box(current.height, Math.max(current.width, current.depth), Math.min(current.width, current.depth));
boxes[i*3 + 1] = new Box(current.width, Math.max(current.height, current.depth), Math.min(current.height, current.depth));
boxes[i*3 + 2] = new Box(current.depth, Math.max(current.height, current.width), Math.min(current.height, current.width));
}

Arrays.sort(boxes, Comparator.comparing(x -> x.area, Comparator.reverseOrder()));
N *= 3;

int[] maxHeights = new int[N];
for (int i = 0; i < N; i++) {
maxHeights[i] = boxes[i].height;
}

for (int i = 0; i < N; i++) {
int maxHeightBeforeI = 0;
for (int j = 0; j < i; j++) {
if (boxes[j].width > boxes[i].width && boxes[j].depth > boxes[i].depth)
maxHeightBeforeI =  Math.max(maxHeightBeforeI, maxHeights[j]);
}
maxHeights[i] = maxHeightBeforeI + boxes[i].height;
}

return Arrays.stream(maxHeights).max().getAsInt();
}

public static void main(String[] args) {
Box[] arr = new Box[4];
arr[0] = new Box(4, 6, 7);
arr[1] = new Box(1, 2, 3);
arr[2] = new Box(4, 5, 6);
arr[3] = new Box(10, 12, 32);

System.out.println(findMaxHeight(arr, 4));
}
}
``````