How can you determine what set of boxes will maximize nesting?

213 Views Asked by At

I'm trying to find a dynamic solution to the nesting boxes problem.

You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can be nested inside of each other.

So more formally,

Given a set $B = \{b_1, b_2, . . . b_n\}$, where each $b_i$ represents a box with a width, height and depth, find the set of boxes that will allow you to nest as many as possible together.

1

There are 1 best solutions below

4
On

$B$ can be equipped with the structure of a poset: we may say that $b_i\leq b_j$ if the box $b_i$ fits inside the box $b_j$. We are looking for the longest chain(s) in such a poset, hence we may recognize the maximal elements, put them in a set $M$, then recognize the minimal elements, put them in a set $m$, then look for the longest path from $m$ to $M$. Mirsky's theorem ensures that the length of the longest chain equals the minimum number of antichains providing a partition of $B$.