箱子堆放问题

  • Z时代
  • 2024-01-10
  • 分类：问答

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

您将得到一组n种类型的矩形3-D框，其中第i个框的高度为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] =如果最后一个塔必须为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/

以上是 箱子堆放问题 的全部内容， 来源链接： utcz.com/qa/411729.html

回到顶部