图论中的盒子堆叠问题

Question

图论中的盒子堆叠问题

algorithmgraphgraph-algorithm

5

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

我们有n个三维盒子。我们可以调整它们的方向，并将它们放在另一个盒子的顶部以获得最大高度。如果一个盒子的两个维度（宽度和长度）小于下面的盒子的尺寸，我们可以将一个盒子放在另一个盒子上面。

例如，我们有3个尺寸w*D*h，我们可以展示它为(h*d,d*h,w*d,d*W,h*w,w*h)。请帮我在图论中解决这个问题。在这个问题中，我们不能将(2*3)放在(2*4)上面，因为它们具有相同的宽度。因此，两个维度应该比盒子小。

- mozhdeh

有没有特定的原因要用图论来解决它？ - TalentTuner

1

请问您需要解决什么问题？您已经说明了如何堆叠箱子，但是您还没有阐明问题。 - moinudin

@ Saurabh因为他可能需要证明这是NP完全问题。我想加上作业标签。 - MK.

这个问题以前已经被提出过：https://dev59.com/mVLTa4cB1Zd3GeqPeNsz（目前得票最高的答案我认为是不正确的，因为它克隆了盒子），还有之前的https://dev59.com/MHE95IYBdhLWcg3wY9D6#2329685（目前被接受的答案是错误的；一个评论给出了反例）。 - Jason Orendorff

2个回答

1

编辑：仅在所有轴无法旋转的情况下有效。

如果我正确理解了问题，它可以通过动态规划来解决。找到最大堆叠高度的简单算法如下：

首先将所有箱子旋转，使得对于箱子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) = max (h_j, max (H(i)|i < j, d_i < d_j, w_i < w_j) + h_j)

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

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

- utdiscant

我认为你忽略了一个重要的事实，即盒子可以任意旋转，使宽度变成高度，反之亦然。 - MK.

@utdiscant，您的公式需要做出小修正： H(j) = max (h_j, max (H(i)|i < j, d_i < d_j, w_i < w_j) + h_j -h_j') 其中，h_j' 是计算高度直到 i 时先前使用的盒子 j 的高度。 - Nandish A

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MK. · Accepted Answer

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

每个盒子变成3个顶点（称之为相关顶点）。得到一个带权有向无环图。修改这里描述的算法。进行拓扑排序（忽略某些顶点相关性），按照该算法操作，但不使用整数数组，而是保留每个顶点路径的列表。当添加通往新顶点（wiki alg 中的 'w'）的路径时，删除包含与 'w' 有关的顶点的通往 'v' 的路径列表，并生成通往新顶点的路径列表。与原始算法不同，此算法是指数级别的。

原始错误答案（请查看评论）：

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