图论中的盒子堆叠
请帮我找到解决这个问题的好方法。
我们有 n 个 3 维的盒子。我们可以调整它们的方向，并且希望将它们放在另一个之上以获得最大高度。如果两个尺寸（宽度和长度）小于下面盒子的尺寸，我们可以将一个盒子放在另一个盒子的顶部。
例如，我们有 3 个维度 w*D*h，我们可以将其显示为 (h*d,d*h,w*d,d*W,h*w,w*h) 请帮我用图论解决这个问题。 在这个问题中，我们不能将(2*3)放在(2*4)之上，因为它具有相同的宽度。所以2维应该小于盒子
Please help me find a good solution for this problem.
We have n boxes with 3 dimensions. We can orient them and we want to put them on top of another to have a maximun height. We can put a box on top of an other box, if 2 dimensions (width and lenght) are lower than the dimensions of the box below.
For exapmle we have 3 dimensions w*D*h, we can show it in to (h*d,d*h,w*d,d*W,h*w,w*h)
please help me to solve it in graph theory.
in this problem we can not put(2*3)above(2*4) because it has the same width.so the 2 dimension shoud be smaller than the box
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
编辑：仅当盒子不能绕所有轴旋转时才有效。
如果我正确理解了这个问题，它可以通过动态规划来解决。找到最大堆栈高度的简单算法是：
首先旋转所有盒子，使得对于盒子 B_i，w_i <= d_i。这需要时间 O(n)。
现在根据底部区域 w_i * d_i 对盒子进行排序，并让索引显示这一点。这需要时间 O(n log n)。
现在，只有当 i < 时，B_i 才能放到 B_j 上。 j，但 i < j并不意味着B_i可以在B_j上。
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 函数并记住索引。
Edit: Only works if boxes can not be rotated about all axes.
If I understand the question correctly, it can be solved by dynamic programming. A simple algorithm finding the height of the maximum stack is:
Start by rotating all boxes such that for Box B_i, w_i <= d_i. This takes time O(n).
Now sort the boxes according to bottom area w_i * d_i and let the indexing show this. This takes time O(n log n).
Now B_i can be put onto B_j only if i < j, but i < j does not imply that B_i can be on B_j.
The largest stack with B_j on top is either
Now we can create a recursive formula for computing the height of the maximum stack
H(j) = max (h_j, max (H(i)|i < j, d_i < d_j, w_i < w_j) + h_j)
and by computing max (H(j),i <= j <= n) we get the height of the maximum stack.
If we want the actual stack, we can attach some information to the H function and remember the indices.
更新（正确？但可能不是最有效的）：
每个盒子变成 3 个顶点（称这些顶点相关）。获取加权 DAG。修改此处描述的算法
按拓扑排序（忽略某些顶点相关的事实），遵循算法，但不保留整数数组，而是保留通向每个顶点的路径列表。然后，当添加新顶点（wiki alg 中的“w”）的路径时，通过删除包含与 w 相关的顶点的 v 的路径来创建通向该顶点的路径列表。
与原始算法不同，这个算法是指数算法。
原始错误答案（见评论）：
每个盒子因其 3 个表面尺寸而变成 3 个节点。然后创建一个有向图，将每个曲面连接到所有较小尺寸的曲面。将价格分配给每条边，使其等于该边通向的节点的第三个维度（即高度）。现在这是寻找DAG中最长路径问题的问题。
UPDATED (correct? but possibly not the most efficient):
Each box becomes 3 vertices (call these vertices related). Get a weighted DAG. Modify the algorithm described here
Sort topologically (ignoring the fact that some vertices are related), follow the algorithm but instead of array of integers keep a list of the paths that lead to each vertex. Then when adding paths for a new vertex ('w' in wiki alg) make a list of paths that lead there by dropping the paths to v that contain a vertex related to w.
Unlike the original algorithm, this one is exponential.
ORIGINAL WRONG ANSWER (see comments):
Each box becomes 3 nodes for its 3 surface sizes. Then create a directed graph connecting each surface to all surfaces of smaller sizes. Assign price to each edge to be equal to the 3rd dimension of the node (i.e. height) that the edge leads to. Now this is the problem of finding the longest path problem in a DAG.