algorithm - 将 N 的长方体分成 M 体积的更小的长方体

Question

我有一个奇怪的具体问题:

将任意大小(整数维度)的长方体分成体积为 4096 或更小的长方体(整数维度)的最有效方法(导致长方体数量最少)是什么？

例如，给定一个 234x45x322 的区域，将它分成长方体的最有效方法是什么？我是否应该制作尽可能多的 16^3 长方体，然后二进制搜索其余的尺寸？我应该试着把它分成大小均匀的矩形吗？

(我将在 Lua 中实现它，但这对解决方案来说并不过分重要)

Answer 1

上限

当考虑一个宽A、深B、高C的矩形盒子时，需要填充盒子的最大体积为4096的长方体数量上限为:

roundUp(A/16) × roundUp(B/16) × roundUp(C/16)

无论您是使用 16×16×16 的立方体来填充大部分矩形框和末端较小的长方体，还是将边分成等长，您永远不需要超过这个数量的长方体。

使用 16×16×16 立方体

使用尽可能多的 16×16×16 立方体来填充矩形框，然后使用较小的立方体来填充其余体积，但这并不能保证获得最佳结果。考虑例如这个例子:

Box size: 43×38×35
Optimal solution: 14 cuboids sized 43×19×5

如果您开始用 8 个大小为 16×16×16 的立方体填充矩形框，则剩余体积由以下部分组成:

slab XY: 32 x 32 x  3  (4096 x 0.75)  
slab YZ: 32 x 32 x 11  (4096 x 2.75)  
slab ZX: 32 x 32 x  6  (4096 x 1.5)  
beam X:  32 x  6 x  3  (4096 x 0.140625)  
beam Y:  32 x  3 x 11  (4096 x 0.2578125)  
beam Z:  32 x  6 x 11  (4096 x 0.515625)  
corner:   6 x  3 x 11  (4096 x 0.04833984375)  

您可以将一个平板与其两个相邻梁中的一个组合起来以创建一个更大的平板，或者将一个平板与两个梁和一个角组合起来以创建一个占据原始长方体的整个边的平板，或者将角组合使用其中一根梁来创建更长的梁，但这些选项都不会造成您只能将剩余体积拆分为 6 个长方体的情况。

^{(图像解释术语；未使用任何数字示例的大小)}

但是，有多个选项可以将剩余体积分成 7 部分，因此整体解决方案是 15 而不是 14，这可能足以作为接近最优的解决方案。

基于此方法的算法需要您考虑 7 个剩余部分的不同组合方式，并找出哪个可以拆分成最少的长方体；这意味着计算一边小于 16 的长方体的最佳分割，这意味着它可以看作是一个更容易解决的二维问题。

需要注意的是，即使剩余部分的总体积小于 4096，由于其 3D L 形状，您总是需要 3 个长方体来填充它。

等长方体

一个简单的方法是通过尝试所有可能的组合来找到具有相同大小长方体的解决方案的最佳大小。由于长方体的体积限制为 4096，因此只需考虑 34,720 种不同的尺寸和方向。

下面的代码示例在 1634 次迭代后找到 43×38×35 示例的最优解，并在 30,183 次迭代后找到 999×9999×99999 的解。如上所述，它永远不需要超过 34,720 次迭代，这使得它非常快，即使在 JavaScript 中也是如此。

function boxCutter(a, b, c) {
    var min = Math.ceil(a / 16) * Math.ceil(b / 16) * Math.ceil(c / 16);
    var solution = {x: 16, y: 16, z: 16, vol: 4096, num: min};
    for (var x = 1; x <= a && x <= 4096; x++) {
        for (var y = 1; y <= b && y <= 4096 / x; y++) {
            var z = Math.floor(4096 / (x * y));
            var num = Math.ceil(a / x) * Math.ceil(b / y) * Math.ceil(c / z);
            if (num < min) {
                min = num;
                solution = {x: x, y: y, z: z, vol: x * y * z, num: min};
            }
        }
    }
    return solution;
}

document.write(JSON.stringify(boxCutter(43, 38, 35)) + "<br>");
document.write(JSON.stringify(boxCutter(999, 9999, 99999)) + "<br>");

组合方法

如果长方体的大小不能均匀地划分矩形框，可以通过对最后一层截断的长方体再次运行算法并用不同大小的长方体填充这部分来获得小的改进，类似于16×16×16 立方体方法的第二阶段。

以一个 999×9999×99999 的矩形框为例，在 243,978,000 个大小为 9×5×91 的长方体中，顶层有 222,000 个高度被截断为 81 的长方体，一层有 121,989 个长方体，其深度被截断为 4。用不同大小的长方体填充这些层中的一个层可分别减少 24,198 和 24,309 的长方体数量，或总数的 0.1% 左右。