代码之家 › 专栏 › 技术社区 › claudius

每个箱子的可能配置

dynamic-programming algorithm

claudius · 技术社区 · 10 年前

问题:给您一组n种矩形三维长方体,其中第i个长方体具有高度h(i)、宽度w(i)和深度D(i)(均为实数)。您希望创建一个尽可能高的长方体堆栈,但如果较低长方体的2-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))+高度(i)},其中j<i和宽度(j)>宽度(i)和深度(j)>深度(i)。如果没有这样的j,则MSH(i)=高度(i)

4) 为了获得总的最大高度,我们返回max(MSH(i)),其中0<i<n

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

2 回复 | 直到 10 年前

Gassa 10 年前

请注意:

为了简单起见,我们认为深度总是小于或等于宽度。

因此,如果一个盒子的尺寸是,例如,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 。这就是它工作的原因。

j_random_hacker 10 年前

不,考虑每个盒子的3个“旋转”就足够了,因为要考虑的唯一可能性是 使盒子顶部和底部垂直于哪个尺寸 ,其中只有3个。用这种方式来考虑每个盒子的3种不同的可能性,而不是旋转,可能会有所帮助。

主要的一点是,在我们选择了盒子的哪对边将是顶部和底部(我们可以用三种方式做到这一点)之后,我们不需要尝试盒子在平面中的两种不同旋转。我们总是可以按照盒子宽于盒子深的旋转。我们如何知道这样做不会错过任何潜在的好解决方案?因为在任何有一个比宽更深的盒子的解决方案中,必须有一个最低的盒子b,并且盒子和上面的所有东西都可以安全地旋转90度。(我们知道这样做是安全的,因为它是解决方案中最低的一个这样的盒子——所以它下面的盒子(如果有的话)必须比它深,这意味着如果我们旋转b 90度,它仍然必须放在这个较低的盒子里(我建议用代数方法验证)。)我们可以在不改变解决方案高度的情况下,不断变换解决方案中比宽框更深的最低值,直到没有剩余值。因为我们可以这样做任何包含一个或多个比宽框更深的解决方案,这意味着每一个解决方案在质量上完全等同于某个解决方案,其中每个框都比深框宽,因此我们可以完全忽略前面的解决方案。