4

给定一组 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'] )

其中 h[j'] 只不过是如果第 j 个框已经用于计算 H[i] 。由于允许旋转，H[j] 可以是第 j 个框的宽度或深度

4

2 回答 2

0

该结果最初是针对 2D 情况得出的，但仍适用于 3D 框，如最后所述。

如果最佳塔中的所有盒子都或可以与它们的长尺寸 EW 对齐，那将是很方便的。

假设一组具有最佳塔的盒子需要一些（非零）数量的盒子同时面向 EW 和 NS。旋转这样的塔，使最底部的盒子与 EW 对齐。现在考虑最低的框 i，它是对齐的 NS。显然盒子 i 的长尺寸小于它的支持盒子 i-1 的最小尺寸；所以盒子 i 的长尺寸小于盒子 i-1 的长尺寸。

同样，由于框 i 的短维度小于框 i 的长维度，通过传递性我们知道框 i 的短维度小于框 i-1 的短维度。因此，从盒子 i 向上的整个子塔可以旋转 90 度以对齐盒子 i EW。

重复当我们登上塔时，很明显所有盒子都可以在任何最佳塔中 EW 对齐。

因此，每个盒子在最佳塔中只有这些可能的“方向”：

  • 高度定向：最长垂直尺寸，第二长定向 EW；
  • 面向长度：最长尺寸 EW，第二长尺寸垂直；
  • 面向宽度：最长尺寸 EW，第二长尺寸面向 NS；
  • 缺席的。
于 2013-03-08T19:44:38.817 回答
-1

您可以在您提供的链接中使用 DP 解决方案，并通过在每个位置设置一个大小为 n 的位图来摆脱“无重复”约束。

这听起来确实像您计划的解决方案，但我并没有完全遵循您的公式或代码。

每个框的索引在它的 3 次旋转之间是通用的，并且设置了位图中用于框索引的位以确保不会处理同一框的下一次旋转。

for i = 1:n  
  Box b = inputi  
  (h3i  , w3i  , d3i  ) = getRotation1(b)  
  (h3i+1, w3i+1, d3i+1) = getRotation2(b)  
  (h3i+2, w3i+2, d3i+2) = getRotation3(b)  
  index3i = index3i+1 = index3i+2 = i

// sort the 4 fields simultaneously (hi, wi, di, indexi all belong to the same box)
// (easy to do in OOP by storing these 4 in the same object)
sortByAreaDesc(h, w, d, index)

H[0] = 0
bitmap0 = {false}

for j = 1:3n
  H[j] = maxi < j, wi > wj, di > dj { if (bitmapj[ indexi ]) 0 else H[i] } + hj  
  bitmapj = bitmapi from max
  bitmapj[ indexi from max ] = true

return maxj H[j]

花费O(n 2 ) 时间和空间。

于 2013-03-08T20:55:04.963 回答