31

我在很多地方都发现了这个著名的 dp 问题，但我不知道如何解决。

给定一组 n 种类型的矩形 3-D 框，其中第 i^th 框的高度为 h(i)，宽度为 w(i)，深度为 d(i)（均为实数）。您想创建一个尽可能高的盒子堆叠，但如果下层盒子的 2-D 底座的尺寸每个都严格大于 2-D 盒子的尺寸，您只能将一个盒子堆叠在另一个盒子的顶部。上盒的 D 底座。当然，你可以旋转一个盒子，让任何一面作为它的基础。也允许使用同一类型盒子的多个实例。

这个问题对我来说似乎太复杂了，无法弄清楚步骤。因为它是 3D，所以我得到了高度、宽度和深度的三个序列。但是由于可以交换 3 维，所以问题对我来说变得更加复杂。所以请有人解释在没有交换时解决问题的步骤，然后在交换时如何做。我厌倦了这个问题。所以，请有人解释解决方案的简单方法。

4

5 回答 5

26

我认为您可以使用动态规划最长递增子序列算法来解决这个问题：http ://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

考虑旋转很容易：对于每个塔，您只需检查如果您使用它的高度作为底座的长度和它的宽度作为高度会发生什么，以及如果您以自然方式使用它会发生什么。例如：

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

变成类似的东西（是的，我知道它看起来不像它应该的样子，只需遵循符号）：

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

因此，对于每个块，您实际上有 3 个块代表其可能的旋转。根据这个调整你的块数组，然后通过减少基面积进行排序，然后应用 DP LIS 算法来获得最大高度。

调整后的递归是： D[i] = 如果最后一个塔必须是 i，我们可以获得的最大高度。

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

在这里观看解释这一点的视频： http ://people.csail.mit.edu/bdean/6.046/dp/

于 2010-02-24T21:28:02.407 回答
6

堆栈可以看作是 x,y,z 三元组的序列（x,y 是二维平面，z 是高度），其中 x(i) > x(i+1) 并且 y(i) > y( i+1)。目标是最大化从可用三元组中挑选三元组的 z 的总和——每个三元组是特定方向的一种类型的盒子。很容易看出，执行约束 x > y 不会减少解决方案空间。所以每个盒子生成 3 个三元组，每个 w,h,d 作为 z 坐标。

如果您将三元组视为有向无环图，其中当两个三元组之间满足 x,y 约束时，长度为 z 的边存在于它们之间，那么问题在于找到通过该图的最长路径。

于 2010-02-24T21:29:52.900 回答
3

让我们首先尝试在二维中解决这个问题：

假设您有带有 X 和 Y 的矩形，问题类似（最高的塔，但这次您只需要担心一个基本尺寸）。
所以首先，你遍历整个集合，通过将每个矩形旋转 90 度（交换 X 和 Y）来复制每个矩形，除了正方形（其中 X(1)=X(2) && Y(1)=Y(2)） . 这代表了所有可能的变化。
然后你按它们的 X 侧对它们进行排序，从大到小。如果 X 值重复，则删除 Y 值较低的那个。

在 3-D 场景中应用相同的原则，只是现在您不只是将集合的大小乘以 6（W、H、D 的所有可能变体）而是乘以 2。您可以通过消除宽度较低的所有变体来做到这一点比深度（所以对于每个 i，W(i)>=D(i)），然后忽略高度不是三个维度中最高或最低的变化（因为其他两个变化可以继续在另一个之上，这个不能加入）。同样，您也忽略了重复（其中 W(1)=W(2) && H(1)=H(2) && D(1)=D(2)）。
然后你应该按宽度排序，只是这次你不要丢弃具有相同宽度的变化（因为一个可能适合另一个可能不适合的塔）然后你可以使用@IVlad 上面描述的 LIS 算法：

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

诀窍是，你知道宽度是两者中最长的，所以你知道第一个元素将不适合任何后面的元素。

于 2010-02-24T21:56:00.503 回答
0

我建议您创建一棵树（或某种树结构）并使用深度搜索对其进行解析，根据各个垂直“高度”（取决于旋转）值计算最大高度。

这（我认为这是基本方法）。

细节大于细节：

树根应该是任何立方体适合的地板。从那里您只需创建可能的下一个（可以放置在当前框顶部的特定旋转中的框）框的子节点。递归地为每个框和旋转执行此操作。

建造树时，通过它并计算从地板到树叶的总塔高。

于 2010-02-24T21:16:03.183 回答
0

该问题的解决方案包括三个步骤。

  1. 对每个框的尺寸进行排序，以便比较任何两个框减少到比较它们对应的尺寸。
  2. 按字典顺序对框的序列进行排序，以便对于每个框，左侧的框是可能适合的框。
  3. 将算法应用于最长递增子序列问题O(n^2)。

第三步是最昂贵的，并且会增加解决方案的复杂性O(n^2)。如果您想阅读该方法的完整说明、每个步骤如何有助于找到答案以及完整代码，请查看我写的关于该问题的博客文章。

于 2016-04-09T18:30:12.927 回答