将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立方体,然后在体积的其余部分使用较小的长方体,但不能保证最佳效果.考虑例如这个例子:

箱尺寸:43×38×35
最佳解决方案:14个长方体,尺寸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的长方体的最佳分裂,这意味着它可以被视为2D问题,这更容易解决.

应该注意的是,即使剩余部件的总体积小于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%.