algorithm - 箱子堆叠问题

Question

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

You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

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

Answer 1

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

计算旋转非常简单:对于每座塔，您只需检查如果将其高度用作底部长度并将其宽度用作高度会发生什么，以及如果您以自然方式使用它会发生什么.例如:

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

变成类似的东西(是的，我知道它看起来不像它应该的样子，只要遵循符号):

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

因此对于每个 block ，您实际上有 3 个 block 代表其可能的旋转。根据此调整您的 block 数组，然后按减少的底面积排序，只需应用 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/