algorithm - 盒堆叠变体-动态规划

Question

问题 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".

不清楚如何根据两个维度进行排序。

Answer 1

我认为这个问题不需要动态规划，这是我的建议:

1. 创建一个图 G，其顶点集 V - 表示所有板，没有边。 ( O(|V|) )

2. 对于 V 中的每一对平板 i 和 j，检查一个是否可以在另一个之上(比较任何维数)。假设 slab i 可以在 slab j 之上，向图中添加一条边 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)

3. 在 G 中找到最长的路径。此路径表示具有最大板数的堆栈。

   在 DAG 中找到这样的路径是一项简单的任务，可以在 linear time 中执行(O(|V|+|E|))。

该算法的总运行时间为O(|V|) + O(|V|^2) + O(|V|+ |E|) = O(|V|^2)。