A question I saw in my sibling’s primary school math homework leads to the following generalization:

Find the maximum number of $l\times w\times h$ bricks one can pack into a $L\times W\times H$ box.

where $l, w, h, L, W, H$ are some given constants (of course for a primary school student).

We assume all faces of the bricks must be parallel to the box face, and all lengths are integers.

Approach 1

If every brick must have the same orientation (e.g. every brick’s $l\times w$ face is parallel to the box’s $L\times W$ face), what is the maximum number of bricks that fit?

Simply try each orientation and take the best count:

$$ \text{answer} = \max_\text{$(x,y,z)$ is a permutation of $(l,w,h)$} (\left\lfloor\frac{L}{x}\right\rfloor\left\lfloor\frac{W}{y}\right\rfloor\left\lfloor\frac{H}{z}\right\rfloor) $$

Approach 2

Every brick may have a different orientation, i.e. bricks can be rotated individually.

We can solve this using dynamic programming, which comes from the intuition that a bad placement early on can waste space and prevent the layout from reaching the true maximum.

One can think of it as: how many $l\times w\times h$ bricks can be cut from the large $L\times W\times H$ box by slicing the box into smaller cuboids?

State

Let $F(x, y, z)$ be the maximum number of bricks that can be packed into an $x\times y\times z$ cuboid.

Base Case

The recursion bottoms out when the cuboid has no volume: if any of $x, y, z$ is $0$, then $F(x,y,z) = 0$.

Note this is the only base case the recursion needs. A small-but-nonempty cuboid like $1\times1\times1$ (when no brick fits) also yields $0$, but that falls out naturally: no orientation fits in Choice 1 (see below), and every cut in Choice 2 produces a sub-cuboid that likewise yields $0$. So “can’t hold a brick” is an emergent result, not a termination condition to check for.

State Transitions

For a $x\times y\times z$ cuboid, there are two choices:

  1. Fill the whole cuboid with all bricks with the same orientation. For each permutation $(a,b,c)$ of $(l, w, h)$ that fits (i.e. $a\le x$, $b\le y$, $c\le z$), we can place $\left\lfloor\frac{x}{a}\right\rfloor \left\lfloor\frac{y}{b}\right\rfloor \left\lfloor\frac{z}{c}\right\rfloor$ bricks. We denote the set of permutation $(a,b,c)$ that fits such bricks $o$, namely:

    $$ o=\{(a,b,c) : \text{permutation of } (l,w,h) \text{ with } a\le x,\; b\le y,\; c\le z\} $$

  2. Cut the cuboid into two smaller ones. E.g. cutting an $x\times y\times z$ cuboid at $x = i$ yields two smaller cuboids $i \times y \times z$ and $(x-i) \times y\times z$. We cut the cuboid from all the three directions $x, y$, and $z$.

$$ F(x,y,z) = \max\begin{cases} \lfloor\frac{x}{a}\rfloor \lfloor\frac{y}{b}\rfloor \lfloor\frac{z}{c}\rfloor & (a,b,c) \in o\\ F(i,y,z) + F(x - i, y, z) & 1 \le i < x\\ F(x,j,z) + F(x, y-j,z) & 1 \le j < y\\ F(x,y,k) + F(x, y, z - k) & 1 \le k < z \end{cases} $$

Time Complexity

$O(LWH(L+W+H))$

Why this is hard in general

Our exact problem packs many copies of a single rotatable brick. It’s tempting to call this NP-hard by pointing at 2-D rectangle packing (set $H = h = 1$), which is known to be NP-hard. But that argument doesn’t actually go through: the NP-hardness of 2-D packing relies on packing rectangles of many different sizes, whereas flattening our problem only ever produces copies of one congruent rectangle. The hard instances of general rectangle packing aren’t reachable as special cases of ours, so this reduction doesn’t establish hardness for the identical-brick problem.

So I’ll be careful about the claim: I don’t have a clean reduction proving the single-brick version is NP-hard, and it may well be easier than general packing. What I can say firmly is that the guillotine DP below solves a restricted version exactly and in polynomial time, and that no simple greedy rule is known to be exact for the unrestricted version. Whether the unrestricted single-brick problem is polynomial or NP-hard is a question I’m leaving open here rather than asserting.

An exact method for the unrestricted version can’t rely on the guillotine shortcut, so it must search over genuine placements. That doesn’t mean naive brute force — ILP and CP-SAT solvers are exact and prune aggressively — but in the worst case the search space is exponential, and no polynomial-time exact algorithm is known.

Limitations

This DP only considers layouts that can be produced by recursive straight (“guillotine”) cuts. Some optimal packings interlock in ways no sequence of full-width cuts can reproduce, so the DP can occasionally undercount by a brick or two.

The reason to accept this isn’t NP-hardness directly — it’s a deliberate trade. Restricting to guillotine layouts is exactly what buys us polynomial time. We’re solving an easier, well-structured sub-problem on purpose, getting a fast and usually-optimal answer, and giving up the guarantee of exactness on interlocking cases. If you need the true optimum, you switch to an exponential search (backtracking or an ILP/CP formulation) and pay for it in runtime.