algorithm - 动态规划 : box stacking variation

Question

我们有 n 个盒子，其尺寸为 x、y、z(宽度、高度、深度)。我们想在另一个里面插入最多数量的盒子。
如果内框 (i) 的大小严格小于外框 (j) 的大小，则可以将一个框放在另一个框内:x[i] < x[j], y[i] < y[j ], z[i] < z[j].
盒子不能旋转，可以按任何顺序考虑。

如何通过动态规划实现目标？
问题类似于最长递增子序列问题？
按升序/降序排列盒子是否有意义？

Answer 1

对盒子进行拓扑排序，排列成图如下: 每个盒子是图中的一个节点，从节点A到节点B的每条有向弧表示对应的盒子A持有盒子B。扩充这个结构有一个无限大小的盒子和一个零大小的盒子。

作为一种拓扑排序，这个图将是一个有向无环图。因此，寻找最长路径不是 NP-hard，而是可以在 O(V+E) 中解决。两个增广框之间的最长路径包含问题的答案。

设置排序的时间复杂度为 O(V^2)，从排序的图形中找到解决方案的时间为 O(V+E)，在此上下文中为 O(V^2)，这是您的整体解决方案时间。