图论中的盒子堆叠

Question

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

我们有n个3维的盒子.我们可以定位它们,我们希望将它们放在另一个上面以获得最大高度.如果2个尺寸(宽度和长度)低于下面方框的尺寸,我们可以将盒子放在另一个盒子的顶部.

为了exapmle我们有3个维度w*D*h,我们可以显示它(h*d,d*h,w*d,d*W,h*w,w*h)请帮我解决它图论.在这个问题上我们不能把(2*3)放在上面(2*4),因为它有相同的宽度.所以2维应该小于盒子

Answer 1

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

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

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

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