1
$\begingroup$

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 set B = {b_1, b_2, . . . b_n} where each b_i contains a box with a width, height and depth.

Find the set of boxes that will allow you to nest as many as possible together.

$\endgroup$
2
  • $\begingroup$ Take $T=[b_1, \dots, b_n]$ an array containing the boxes. $T_w$ the result of sorting $T$ according to width. Similarly for $T_h$ and $T_d$. Now if $b_i \subseteq b_j$, then $b_i$ is before $b_j$ in all $3$ arrays. So you can extract a longest common subsequence of those three arrays (using a well-known dynamic programming algorithm) and it will be a maximal nesting. Or you can get inspiration from this reduction to build an ad-hoc algorithm (which is probably a better idea if you're trying to familiarize yourself with the method). $\endgroup$
    – xavierm02
    Oct 19, 2016 at 21:50
  • $\begingroup$ What have you tried? Please read our tag guidance cs.stackexchange.com/tags/dynamic-programming/info and edit your question to show what you've tried. Have you tried following the approach at cs.stackexchange.com/q/47216/755 and cs.stackexchange.com/q/645/755? How far did you get, and what are you stuck on? See also cs.stackexchange.com/q/2057/755 and meta.cs.stackexchange.com/q/1284/755. $\endgroup$
    – D.W. ♦
    Oct 20, 2016 at 18:24

1 Answer 1

Reset to default
3
$\begingroup$

Let $\le_B$ denote the inclusion relation between boxes, i.e. $b_i\le_B b_j$ if we can put the box $b_i$ inside $b_j$. Obviously $\le_B$ is a partial ordering of $B=\left\{b_1,...,b_n\right\}$.

Your question translates to finding the maximal linearly ordered subset of $B$ relative to $\le_B$. A linearly ordered subset is a path in the acyclic directed graph $G$ representing $\le_B$, i.e. $V_G=B$ and $(b_i,b_j)\in E_G\iff b_i\le_B b_j$. We can now reduce your problem into finding the longest path in the DAG $G$. This can be done in linear time with topological sorting. Overall, the time consuming part is constructing $G$, which requires $O(n^2)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.