单位立方体的边长，假设需要使用 N 个单位立方体来 tile/fill 给定尺寸的 3D space
Side length of unit cube, given one needs to use N unit cubes to tile/fill a 3D space of given dimension
其中一个是 3 维直角棱镜 space，例如{xmin, xmax}, {ymin, ymax}, {zmin, zmax}。目标是使用最多 N 个立方体的预定义 "grid" 来最大程度地平铺 3 维 space。如果 N 不能均匀地平铺到 space 中，它将使用不超过 N 个立方体。注意立方体位于立方体中心点（即它是一个网格），而不是立方体边缘。
例如，在 N=30 和 {0,3} 的简单情况下，{0,3}，{0,3}。正确答案是使用边长为 1 的立方体，在这种情况下，将使用 27 个立方体，3 行 3 列，3 叠。
在更难的情况下，N=1000, and {0, 100}, {0, 0}, {0, 50}，显然y维只用了1行立方体（不能用any more), 因此 z 和 x 维度必须使用以 2:1 的比例排列的 1000 个立方体。 100/L * 50/L = 1000。因此，边长可能约为 2.2361，因为 22 x 1 x 45 = 990 是我们最接近 1000 的值（或者，我们已经最小化了我们可以达到的范围不覆盖我们的立方体中心）。当然边数必须是正方体的整数倍。
我正在尝试计算一个方程组来解决这个问题，但我有一种奇怪的感觉，这是一个满足（最小化）问题，因此需要进行一些迭代...这是一次尝试无论如何在方程组：
L, xe, ye, ze ∊ Positive Reals
N, x, y, z ∊ Natural Numbers
x*y*z ≤ N
(x-1)*L ≤ xe
(y-1)*L ≤ ye
(z-1)*L ≤ ze
x,y,z ≥ 1
L = min(i) { (xe*ye*ze) - ((x-1)*i*(y-1)*i*(z-1)*i) }
我把它设置为 x-1、y-1 等，这意味着它们最多可以超出宽度 1 个立方体大小。我无法决定在所有维度上这样做是否正确，或者指定它最多必须在一个维度（最小？）之外。
总体思路
这里的直觉是，每个方向上的立方体数量将与该方向上 space 的大小成正比，因为立方体是规则的。另一个提示是 "how many cubes in each direction" 问题的解决方案仅取决于大小之间的比率，而不取决于它们的实际值：如果您将每个维度乘以相同的膨胀因子，您的解决方案将仍然相同。
简化问题
假设您的 space 大小为 dx, dy, dz，全部非零，并且您想使用最多 N 个立方体。
让我们将约束表达为：
find Nx, Ny, Nz, L such that
- Nx * Ny * Nz ≤ N
- Nx * L ≤ dx
- Ny * L ≤ dy
- Nz * L ≤ dz
Minimizing the "lost volume": (dx * dy * dz - L^3 * Nx * Ny * Nz)
您可能想要最大化 Nx * Ny * Nz。另请注意，最小化未平铺的体积等同于最大化 L^3 * Nx * Ny * Nz.
最后的观察是，如果您的解决方案在任何方面（立方体数量或平铺体积）都是最优的，则至少一个维度将具有相等性 N@ * L == d@，否则我们可能会增加 L.
让我们不失一般性地假设 dx 是这个维度，让我们将所有长度除以 dx，因此 a@ = d@ / dx 对于 @ 是 y 和 z（如果需要，还有 ax = 1）。那么我们可以重写问题：
find Nx, Ny, Nz, L such that
- Nx * Ny * Nz ≤ N
- Nx = dx / L
- Ny / Nx ≤ ay
- Nz / Nx ≤ az
Maximizing the cubes' volume: dx^3 * (Ny / Nx) * (Nz / Nx)
因此，您的问题是如何使每一侧的立方体数量之比尽可能接近尺寸之比，同时保持 Nx * Ny * Nz ≤ N——与您本能地接近 [=29] 的方式相同=] case.
算法建议： 例如，你可以迭代地增加Nx并设置N@ = floor(a@ * Nx) for @ in {y,z} while Nx * Ny * Nz ≤ N, 保留最佳方案。
最优解
请注意，在您的比率 ay 和 az 是有理数的情况下，如您的示例所示，可能很容易找到最小化的精确解。
让我们为{y,z}中的@写a@ = n@ / m@，然后我们可以通过设置
Nx = lcm(my, mz) - 分母的最小公倍数来找到精确解.请注意，在 dx, dy, dz 均为整数的情况下，这意味着 Nx = dx / gcd(dx, dy, dz).
因此如果Nx^3 * ax * ay = lcm(my, mz) ^3 * ny * nz / (my * mz) ≤ N，这个解也符合N的约束。完整写出来：
Nx = lcm(my, mz)
L = dx / Nx
Ny = Nx * ay
Nz = Nx * az
在您的示例中，对于 3D 情况，您有 ay = az = 1 和 Nx = Ny = Nz = 1 的解决方案，对于 2D 情况，我们只有维度 x、z 和 az = 1/2，你有一个 Nx = 2 和 Nz = 1
的解决方案
现在您可以添加更多立方体，因为 Nx * Ny * Nz ≤ N 约束中有很多松弛部分。特别是，您可以将每个坐标乘以 floor(cbrt(N / (Nx * Ny * Nz)))，在第一种情况下为 floor(cbrt(30 / 1)) = 3，在 2D 情况下为 floor(sqrt(1000 / 2)) = 22。
总结你的例子的结果：
space={3,3,3} N=30 : Nx=3, Ny=3, Nz=3, L=1
space={100, 50} N=1000 : Nx=44, Nz=22, L=2.72727272...
启发式
如果找不到确切答案，我们可以进行有根据的猜测。为了不迭代 Nx 值，或者只是为了有一个合理的初始猜测。
注意，分母越大，同分母的两个分数间隔越小。这并不意味着给定一个你想要近似的实数，你的近似精度与分母的大小成正比，但是当近似大量实数时平均精度会更好（因此，你'在单一情况下我们有更好的概率）。
我们试图最大化 (Ny / Nx) * (Nz / Nx)，因此根据我们对 ay 和 az 的约束，我们得到 (N@ + 1) / Nx ≥ a@，因此 N@ ≥ a@ * Nx - 1。
现在，Nx * Ny * Nz ≤ N 因此 Nx 的界限是：
Nx * (Nx * ay - 1) * (Nx * az - 1) ≤ N
但是我懒得解决这个问题所以让我们再简化一些：N@ ≥ a@ * Nx - 1 ≥ a@ * Nx
因此：Nx * (Nx * ay) * (Nx * az) ≤ N
所以你可以先猜一猜：
Nx = floor(crbt(N / (ay * az)))
L = dx / Nx
Ny = floor(Nx * ay)
Nz = floor(Nx * az)
或（完全一样，没有 a@）：
Nx = floor(crbt(N * dx * dx / (dy * dz)))
L = dx / Nx
Ny = floor(dy / L)
Nz = floor(dz / L)
如果你想确保你有最优值，你可能想尝试看看简化是否限制了 Nx 太多，所以增加它直到 Nx * Ny * Nz ≥ N 并保持最佳配置.
同样，Nx 的不同值可能会让 Nx * ay 和 Nx * az 更接近它们的整数部分，从而减少浪费 space。您可以递减 Nx 直到它变小。请注意，您可以跳过任何除以您已经尝试过的 Nx 值的值。
选择"filled dimension"x
仍然是选择 x 的方向——本能地我会说选择你的 space 最大的维度，但这又只是一种启发式的，如果你想要您将不得不尝试所有方向的最佳答案。
不过，在边长比合理的精确解中，选择任何边作为 x 都可以，因为所有维度都将被填充。
其中一个是 3 维直角棱镜 space，例如{xmin, xmax}, {ymin, ymax}, {zmin, zmax}。目标是使用最多 N 个立方体的预定义 "grid" 来最大程度地平铺 3 维 space。如果 N 不能均匀地平铺到 space 中，它将使用不超过 N 个立方体。注意立方体位于立方体中心点（即它是一个网格），而不是立方体边缘。
例如，在 N=30 和 {0,3} 的简单情况下，{0,3}，{0,3}。正确答案是使用边长为 1 的立方体，在这种情况下，将使用 27 个立方体，3 行 3 列，3 叠。
在更难的情况下，N=1000, and {0, 100}, {0, 0}, {0, 50}，显然y维只用了1行立方体（不能用any more), 因此 z 和 x 维度必须使用以 2:1 的比例排列的 1000 个立方体。 100/L * 50/L = 1000。因此，边长可能约为 2.2361，因为 22 x 1 x 45 = 990 是我们最接近 1000 的值（或者，我们已经最小化了我们可以达到的范围不覆盖我们的立方体中心）。当然边数必须是正方体的整数倍。
我正在尝试计算一个方程组来解决这个问题，但我有一种奇怪的感觉，这是一个满足（最小化）问题，因此需要进行一些迭代...这是一次尝试无论如何在方程组：
L, xe, ye, ze ∊ Positive Reals
N, x, y, z ∊ Natural Numbers
x*y*z ≤ N
(x-1)*L ≤ xe
(y-1)*L ≤ ye
(z-1)*L ≤ ze
x,y,z ≥ 1
L = min(i) { (xe*ye*ze) - ((x-1)*i*(y-1)*i*(z-1)*i) }
我把它设置为 x-1、y-1 等，这意味着它们最多可以超出宽度 1 个立方体大小。我无法决定在所有维度上这样做是否正确，或者指定它最多必须在一个维度（最小？）之外。
总体思路
这里的直觉是，每个方向上的立方体数量将与该方向上 space 的大小成正比，因为立方体是规则的。另一个提示是 "how many cubes in each direction" 问题的解决方案仅取决于大小之间的比率，而不取决于它们的实际值：如果您将每个维度乘以相同的膨胀因子，您的解决方案将仍然相同。
简化问题
假设您的 space 大小为 dx, dy, dz，全部非零，并且您想使用最多 N 个立方体。
让我们将约束表达为：
find Nx, Ny, Nz, L such that
- Nx * Ny * Nz ≤ N
- Nx * L ≤ dx
- Ny * L ≤ dy
- Nz * L ≤ dz
Minimizing the "lost volume":(dx * dy * dz - L^3 * Nx * Ny * Nz)
您可能想要最大化 Nx * Ny * Nz。另请注意，最小化未平铺的体积等同于最大化 L^3 * Nx * Ny * Nz.
最后的观察是，如果您的解决方案在任何方面（立方体数量或平铺体积）都是最优的，则至少一个维度将具有相等性 N@ * L == d@，否则我们可能会增加 L.
让我们不失一般性地假设 dx 是这个维度，让我们将所有长度除以 dx，因此 a@ = d@ / dx 对于 @ 是 y 和 z（如果需要，还有 ax = 1）。那么我们可以重写问题：
find Nx, Ny, Nz, L such that
- Nx * Ny * Nz ≤ N
- Nx = dx / L
- Ny / Nx ≤ ay
- Nz / Nx ≤ az
Maximizing the cubes' volume:dx^3 * (Ny / Nx) * (Nz / Nx)
因此，您的问题是如何使每一侧的立方体数量之比尽可能接近尺寸之比，同时保持 Nx * Ny * Nz ≤ N——与您本能地接近 [=29] 的方式相同=] case.
算法建议： 例如，你可以迭代地增加Nx并设置N@ = floor(a@ * Nx) for @ in {y,z} while Nx * Ny * Nz ≤ N, 保留最佳方案。
最优解
请注意，在您的比率 ay 和 az 是有理数的情况下，如您的示例所示，可能很容易找到最小化的精确解。
让我们为{y,z}中的@写a@ = n@ / m@，然后我们可以通过设置Nx = lcm(my, mz) - 分母的最小公倍数来找到精确解.请注意，在 dx, dy, dz 均为整数的情况下，这意味着 Nx = dx / gcd(dx, dy, dz).
因此如果Nx^3 * ax * ay = lcm(my, mz) ^3 * ny * nz / (my * mz) ≤ N，这个解也符合N的约束。完整写出来：
Nx = lcm(my, mz)
L = dx / Nx
Ny = Nx * ay
Nz = Nx * az
在您的示例中，对于 3D 情况，您有 ay = az = 1 和 Nx = Ny = Nz = 1 的解决方案，对于 2D 情况，我们只有维度 x、z 和 az = 1/2，你有一个 Nx = 2 和 Nz = 1
现在您可以添加更多立方体，因为 Nx * Ny * Nz ≤ N 约束中有很多松弛部分。特别是，您可以将每个坐标乘以 floor(cbrt(N / (Nx * Ny * Nz)))，在第一种情况下为 floor(cbrt(30 / 1)) = 3，在 2D 情况下为 floor(sqrt(1000 / 2)) = 22。
总结你的例子的结果：
space={3,3,3} N=30 : Nx=3, Ny=3, Nz=3, L=1
space={100, 50} N=1000 : Nx=44, Nz=22, L=2.72727272...
启发式
如果找不到确切答案，我们可以进行有根据的猜测。为了不迭代 Nx 值，或者只是为了有一个合理的初始猜测。
注意，分母越大，同分母的两个分数间隔越小。这并不意味着给定一个你想要近似的实数，你的近似精度与分母的大小成正比，但是当近似大量实数时平均精度会更好（因此，你'在单一情况下我们有更好的概率）。
我们试图最大化 (Ny / Nx) * (Nz / Nx)，因此根据我们对 ay 和 az 的约束，我们得到 (N@ + 1) / Nx ≥ a@，因此 N@ ≥ a@ * Nx - 1。
现在，Nx * Ny * Nz ≤ N 因此 Nx 的界限是：
Nx * (Nx * ay - 1) * (Nx * az - 1) ≤ N
但是我懒得解决这个问题所以让我们再简化一些：N@ ≥ a@ * Nx - 1 ≥ a@ * Nx
因此：Nx * (Nx * ay) * (Nx * az) ≤ N
所以你可以先猜一猜：
Nx = floor(crbt(N / (ay * az)))
L = dx / Nx
Ny = floor(Nx * ay)
Nz = floor(Nx * az)
或（完全一样，没有 a@）：
Nx = floor(crbt(N * dx * dx / (dy * dz)))
L = dx / Nx
Ny = floor(dy / L)
Nz = floor(dz / L)
如果你想确保你有最优值，你可能想尝试看看简化是否限制了 Nx 太多，所以增加它直到 Nx * Ny * Nz ≥ N 并保持最佳配置.
同样，Nx 的不同值可能会让 Nx * ay 和 Nx * az 更接近它们的整数部分，从而减少浪费 space。您可以递减 Nx 直到它变小。请注意，您可以跳过任何除以您已经尝试过的 Nx 值的值。
选择"filled dimension"x
仍然是选择 x 的方向——本能地我会说选择你的 space 最大的维度，但这又只是一种启发式的，如果你想要您将不得不尝试所有方向的最佳答案。
不过，在边长比合理的精确解中，选择任何边作为 x 都可以，因为所有维度都将被填充。