给定一组 n 种矩形 3-D 框，其中第 i^th 个框的高度为 h(i)、宽度为 w(i) 和深度为 d(i)(均为实数)。您想要创建一堆尽可能高的盒子，但是如果下方盒子的 2-D 底边的尺寸都严格大于 2-D 底边的尺寸，您只能将盒子堆叠在另一个盒子的顶部较高箱子的 D 底座。当然，您可以旋转一个盒子，使任何一侧都作为它的底面。不允许在一个盒子上使用多个实例。
这个问题已经在 SO ( Box stacking problem ) 上被问到，但没有“没有重复”的限制。 我们如何使用 LIS 解决这个问题。
我设计了以下解决方案，是否可以辩论
H[j] = max(H[j],max(H[i]|i<j, D[j] < D[i] , W[j]<W[i]+ H[j] -H[j'] )
where h[j'] is nothing but if the jth box is already used to in computing H[i] . Since rotation is allowed , H[j] could be width or depth of jth box
最佳答案
这个结果最初是针对 2D 情况得出的，但仍然适用于 3D 盒子，如最后所解释的。
如果最佳塔中的所有框都或可以与其长尺寸 E-W 对齐，将会很方便。
假设一组具有最佳塔的盒子，需要一定数量(非零)的盒子同时面向 E-W 和 N-S。旋转这样的塔，使最底部的盒子与东西对齐。现在考虑最低的盒子 i，它是 N-S 对齐的。很明显，盒子 i 的长尺寸小于其支撑盒 i-1 的最小尺寸；所以盒子 i 的长尺寸小于盒子 i-1 的长尺寸。
同样，由于盒子 i 的短尺寸小于盒子 i 的长尺寸，根据传递性我们知道盒子 i 的短尺寸小于盒子 i-1 的短尺寸。因此，从盒子 i 开始的整个子塔可以旋转 90 度以对齐盒子 i E-W。
在我们登上塔楼时重复，很明显，在任何最佳塔楼中，所有盒子都可以东西向对齐。
因此每个盒子在最佳塔中只有这些可能的“方向”:
- 面向高度:纵向最长维度，东西方向第二长；
- 面向长度:最长的东西向维度，第二长的垂直维度；
- 面向宽度:最长维度E-W，次长维度面向N-S；
- 缺席。
关于algorithm - 无重复的箱子堆叠，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15301326/