盒子堆叠问题

Question

我在很多地方发现了这个着名的dp问题,但我无法弄清楚如何解决.

您将获得一组n种类型的矩形3-D盒子,其中第i个盒子具有高度h(i),宽度w(i)和深度d(i)(所有实数).你想要创建一个尽可能高的盒子堆叠,但如果下盒子的2-D底座的尺寸都严格大于2的盒子,你只能在另一个盒子的顶部堆叠一个盒子.高架子的D基座.当然,您可以旋转一个框,以便任何一侧作为其基础.也允许使用相同类型的盒子的多个实例.

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

Answer 1

我认为你可以使用动态编程最长的子序列算法来解决这个问题: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/

Answer 2

堆栈可以被视为x,y,z三元组的序列(x,y是2D平面,z是高度),其中x(i)> x(i + 1)和y(i)> y( I + 1).目标是最大化从可用三元组集合中选择三元组的总和 - 每个三元组是特定方向的一种类型的盒子.很容易看出强制执行约束x> y不会减少解空间.因此每个盒子生成3个三元组,每个w,h,d作为z坐标.

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