问题 1:给定许多板,每个板都有长度和宽度。如果 i 的两个维度都小于 j 的维度,则可以将 slab i 放在 slab j 上。以这种类似的方式,您可以继续将平板放在彼此之上。找到您可以从给定的 slab 中创建的最大堆栈。
问题2:上面的问题被提升到了3维。
问题3:然后将上面的问题提升到k维。
我相信我们可以将动态规划应用于上述问题。但是
"A slab i can be put on slab j if both dimensions of i are less than that of j".
不清楚如何根据两个维度进行排序。
最佳答案
我认为这个问题不需要动态规划,这是我的建议:
创建一个图
G
,其顶点集V
- 表示所有板,没有边。 (O(|V|)
)对于
V
中的每一对平板i
和j
,检查一个是否可以在另一个之上(比较任何维数)。假设 slabi
可以在 slabj
之上,向图中添加一条边i->j
。如果i
和j
的维度相同,则应添加一条边。 (O(|V|^2)
)结果图是 DAG ,因为对于任意 3 个 slab
i,j,k
,如果i
可以在j
之上,并且j
可以在k
之上,那么k
不能在i
之上。为了避免 3 个或更多 slab 大小相同时出现循环(例如
i->j, j->k, k->i
),如果 2 个 slab 大小相同大小,边缘的方向将从较小的索引到较大的索引(例如,如果i
和j
的维度相等,那么我们将添加的边缘是i->j
)在
G
中找到最长的路径。此路径表示具有最大板数的堆栈。在 DAG 中找到这样的路径是一项简单的任务,可以在 linear time 中执行(
O(|V|+|E|)
)。
该算法的总运行时间为O(|V|)
+ O(|V|^2)
+ O(|V|+ |E|)
= O(|V|^2)
。
关于algorithm - 盒堆叠变体-动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22317649/