algorithm - 每个盒子的可能配置

Question

问题:给定一组 n 种矩形 3-D 框，其中第 i^th 个框的高度为 h(i)、宽度为 w(i) 和深度为 d(i)(均为实数)。您想要创建一堆尽可能高的盒子，但是如果下方盒子的 2-D 底边的尺寸都严格大于 2-D 底边的尺寸，您只能将盒子堆叠在另一个盒子的顶部较高箱子的 D 底座。当然，您可以旋转一个盒子，使任何一侧都作为它的底面。也允许使用同一类型框的多个实例。

解决方案:我在 http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/ 找到了以下解决方案

1) 生成所有框的所有 3 个旋转。旋转数组的大小变为原始数组大小的 3 倍。为简单起见，我们认为深度总是小于或等于宽度。

2) 将上面生成的3n个盒子按照底面积从大到小的顺序进行排序。

3) 对框进行排序后，问题与具有以下最优子结构属性的 LIS 相同。MSH(i) = 最大可能的堆叠高度，盒子 i 位于堆叠顶部MSH(i) = { Max ( MSH(j) ) + height(i) } 其中 j < i 和 width(j) > width(i) 和 depth(j) > depth(i)。如果没有这样的 j 那么 MSH(i) = height(i)

4) 为了获得整体最大高度，我们返回 max(MSH(i)) 其中 0 < i < n

我认为这个解决方案是错误的，因为它只考虑了所有盒子的 3 次旋转。为了得到正确的解决方案，它应该生成 6 个可能的旋转。那么，给定的解决方案是否不正确，或者他们在使用 6 次旋转时是否有任何缺陷？

Answer 1

请注意:

For simplicity, we consider depth as always smaller than or equal to width.

所以，如果一个盒子的尺寸是，例如，3、4、5，我们考虑以下三种方式将它放入堆栈:

• d=3, w=4, h=5
• d=3, w=5, h=4
• d=4, w=5, h=3

其他三个旋转的深度大于宽度，所以我们不考虑它们:

• d=4, w=3, h=5
• d=5, w=3, h=4
• d=5, w=4, h=3

为了查看是否有一个矩形a x b可以被另一个完全覆盖c x d , 将它们都转动就足够了 a <= b和 c <= d , 然后检查是否 a <= c和 b <= d .这就是它起作用的原因。