•  22-09-2019
  •  | 
  •  

题

我找到了这个着名的dp问题在许多地方，但是我不能找出如何解决。

给你一个组n类型的 矩的3-D框，在那里我^个 框中具有高度h(i)、宽w(i)和 深d(i)(所有的现实数字)。你的 希望创建一堆箱 是因为高成为可能，但你可以 只有一堆盒子上的另一个盒子 如果的尺寸2-D座的 下框每严格大 比2-D座的 高箱。当然，你可以旋转 一个盒子所以，任何一侧的功能 它的基础。它还允许使用 多个同一型的 盒。

这个问题似乎太复杂我以图出的步骤。因为它是3D，我得到三个序列的高度、宽度和深度。但是，因为它可能交换的3个层面的问题变得更加复杂了我。所以请别人解释的步骤，以解决的问题时，没有交换然后如何做到这一点时交换。我累了关于这个问题。所以请，请人解释解决方案简单的方法。

有帮助吗？

解决方案

我觉得你可以解决这一使用动态规划 最长的增加子序列 算法： http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

会计的旋转是容易的：每塔你必须检查是会发生什么，如果你用它的高度作为长的基础和它的宽度作为高度和发生什么，如果你用它的自然的方式。例如：

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

变成什么样的(是的，我知道这看起来没有像它应该只是按照符号): 

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

因此，对于每个区块，你实际上有3块表示其可能的旋转。调整你的块阵列根据这一点，然后通过减少基地区和只适用于DP LIS算法得到最大的高度。

的适合于重复是：D[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.

看到视频explaning这个在这里： http://people.csail.mit.edu/bdean/6.046/dp/

其他提示

栈可以视为X，Y，Z的三元组的序列（X，Y为2D平面和z的高度），其中，x（I）> X（I + 1）和Y（I） > Y（I + 1）。我们的目标是最大化的z从一组可用三胞胎采摘三胞胎的总和 - 每个三联是在一个特定的方向上的一个类型的框。这是很容易看到，实施该约束X> Y不降低溶液的空间。因此，每个框生成3个三重峰，具有各自的W，H，d为z坐标。

如果你把三胞胎为有向非循环图，其中，当在x，y约束在它们之间满意的两个三联之间长度z存在的边缘，则该问题是通过图中发现的最长路径的

让我们首先尝试在2- d解决这个问题：

说你有X和Y的矩形，问题是相似的（最高的塔，但这个时候你只需要大约一个基本维度担心）。结果 所以第一，你去在整个收集，通过旋转90度（换X和Y）的每一个复制矩形，除了正方形（其中X（1）= X（2）&& Y（1）= Y（2）） 。这代表了所有可能的变化。结果 那么你可以通过X侧对它们进行排序，从最大到最小。一式两份X值的情况下，删除所述一个与下一个Y值。

同样的原则在3 d场景应用，只是现在您可以通过6（在W的每一个可能的变型，H，d）DONT只是乘集合的大小，而是通过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.

的诀窍是，要知道的是，宽度是最长的两个，所以你知道第一个元素将不适合于以后的任何元件的顶部上。

建议你创建树（或某种树结构的），并与深度搜索解析它，从各个垂直“高度”计算最大高度（depening上旋转）的值。

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

详细细节上：

树根应该是在地板上，其中，任何立方体配合到。从那里，你只需要创建的下一步可能（盒可以放置在当前框一定的旋转ontop的）框的子节点。 Recursivly做，对于每个框和旋转。

当树是构建，通过它和从calc下的总塔heigth 地板向树的叶。

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

  1. 对每个盒子的尺寸进行排序，以便比较任意两个盒子减少为比较它们相应的尺寸。
  2. 按字典顺序对框序列进行排序，以便对于每个框，左侧的框是可以容纳的框。
  3. 申请 这 O(n^2) 最长递增子序列问题的算法.

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top