将 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)

您可以将一块板与它的两个相邻梁之一组合起来，以创建一个更大的板，或者将一个板与两个梁和角组合起来，以创建一个占据原始长方体的整个边的板，或者组合一个梁的角可以创建一个更长的梁，但是这些选项中的 none 会创建一种情况，您可以将剩余的体积拆分为仅 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的长方体为例，在9×5×91的243,978,000个长方体中，有顶层222,000个高度被截断为81的长方体，还有一层121,989个长方体其深度被截断为 4。用不同大小的长方体填充这些层中的一个层可分别减少 24,198 和 24,309 的长方体数量，或总数的 0.1% 左右。

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

Dividing a cuboid of N into smaller cuboids of M volume

algorithm

lua

geometry

rectangles