有多少个大小为 a×a 的正方形可以装入一个半径为 R 的圆中？

我不需要解决方案。我只需要一些开始的想法。

最佳答案

很抱歉写了这么长的答案。我的方法是从理论上的最大值和保证的最小值开始。当您处理问题时，您可以使用这些值来确定您使用的任何算法的好坏。如果您能想到更好的最小值，那么您可以改用它。

我们可以简单地使用圆的面积来定义问题的上限

其中 L 是您要打包的正方形的宽度或高度，r 是您要将正方形打包成的圆的半径。我们确信这是一个上限，因为 a) 我们必须有离散数量的框和 b) 我们不能占用比圆面积更多的空间。 (一个正式的证明会在某个地方起作用，假设我们有一个比这更多的盒子，那么盒子的面积之和将大于圆的面积)。

因此，有了上限，我们现在可以采用对所有圆都存在的任何解决方案，并将其称为最小解决方案。

因此，让我们考虑一个适用于所有圆的解决方案，方法是查看我们可以放入圆内的最大正方形。

圆内可以容纳的最大正方形在周长上有 4 个点，宽度和长度为 sqrt(2) * radius(通过使用毕达哥拉斯定理并将半径用于短边的长度)

所以我们首先要注意的是，如果 sqrt(2) * radius 小于正方形的尺寸，那么您就不能在圆中放置任何正方形，因为毕竟这是您可以容纳的最大正方形。

现在我们可以做一个简单的计算，使用您指定的 L 将这个大正方形分成规则的正方形网格，这将为我们提供至少一个问题的解决方案。所以你在这个最大正方形内有一个正方形网格。您可以放入此网格的一行中的方 block 数是

因此这个最小解断言你至少可以拥有

圆内的方 block 数。

因此，如果您迷路了，我所做的就是取圆圈内可以放入的最大正方形，然后将尽可能多的正方形填充到圆圈内的规则网格中，至少给我一个解决方案。

如果您在此阶段得到的答案为 0，则您无法在圆圈内放置任何正方形。

现在有了理论最大值和绝对最小值，您可以开始尝试使用您喜欢的任何类型的启发式算法来打包正方形。一个简单的算法是将圆分成几行，并在每一行中放入尽可能多的正方形。然后，您可以将此最低限度作为指导，以确保您提出更好的解决方案。如果您想花费更多的处理能力来寻找更好的解决方案，您可以使用理论作为指导，了解您与理论最佳值的接近程度。

如果你关心这个，你可以计算出我确定的最小算法覆盖率的最大和最小理论百分比。最大的正方形始终覆盖固定比例(我认为是 pi/4 或约 78.5% 的圆内部面积)。因此，最大理论最小值是 78.5% 的覆盖率。最小非平凡(即非零)理论最小值是当你只能在最大正方形内放置 1 个正方形时，当​​你正在打包的正方形比你能容纳的最大正方形的宽度和高度的一半大时，就会发生这种情况适合在圈子里。基本上你用 1 个填充方 block 占据了超过 25% 的内部方 block ，这意味着你得到大约 20% 的覆盖率

关于algorithm - 一个圆可以装多少个正方形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9537333/