algorithm - 图论中的盒子堆叠

Question

请帮我找到解决这个问题的好方法。

我们有 n 个 3 维的盒子。我们可以定位它们，并且我们希望将它们放在另一个之上以获得最大高度。如果两个尺寸（宽度和长度）小于下面盒子的尺寸，我们可以将一个盒子放在另一个盒子的顶部。

例如，我们有 3 个维度 w*D*h，我们可以将其显示为 (h*d,d*h​​,w*d,d*W,h*w,w*h) 请帮我解决它图论。在这个问题中，我们不能将（2*3）放在（2*4）之上，因为它具有相同的宽度。所以二维应该小于盒子

Answer 1

更新（正确？但可能不是最有效的）：

每个框变成 3 个顶点（称这些顶点相关）。获取加权 DAG。修改此处描述的算法 拓扑排序（忽略某些顶点相关的事实），遵循算法，但保留通向每个顶点的路径列表，而不是整数数组。然后，当为新顶点添加路径时（wiki alg 中的“w”），通过将包含与 w 相关的顶点的路径删除到 v 来制作通往那里的路径列表。与原始算法不同，这个算法是指数的。

原始错误答案（见评论）：

每个盒子因其 3 个表面尺寸而成为 3 个节点。然后创建一个有向图，将每个表面连接到所有较小尺寸的表面。将价格分配给每条边，使其等于边所通向的节点的第三维（即高度）。现在这是在 DAG 中寻找最长路径问题的问题。

Answer 2

编辑：仅当框不能围绕所有轴旋转时才有效。

如果我正确理解了这个问题，它可以通过动态编程来解决。找到最大堆栈高度的简单算法是：

首先旋转所有框，使得对于框 B_i，w_i <= d_i。这需要时间 O(n)。

现在根据底部区域 w_i * d_i 对框进行排序，并让索引显示这一点。这需要时间 O(n log n)。

现在只有当 i < j 时 B_i 才能放在 B_j 上，但 i < j 并不意味着 B_i 可以放在 B_j 上。

顶部有 B_j 的最大堆栈是

• B_j 在地上
• 由前 j-1 个盒子组成的堆栈，顶部是 B_j。

现在我们可以创建一个递归公式来计算最大堆栈的高度

H(j) = 最大值 (h_j, 最大值 (H(i)|i < j, d_i < d_j, w_i < w_j) + h_j)

通过计算 max (H(j),i <= j <= n) 我们得到最大堆栈的高度。

如果我们想要实际的堆栈，我们可以将一些信息附加到 H 函数并记住索引。