algorithm - 最大化放置在圆中的矩形所使用的面积

Question

我有一个圆圈，我需要用矩形填充。一个叠在另一个上面。矩形仅提供特定尺寸。我们还得到了必须放置的矩形的数量。我需要得到一组覆盖圆的大部分区域的矩形长度。例如，如果圆的直径为 100，则可以放置长度为 [100,95,90,85,...15,10,5] 的矩形。我试过通过解析所有可能的组合使用蛮力方法。当数字很小时会产生很好的结果。我尝试的另一种算法是限制每个矩形占据的长度范围。就像第一个矩形的长度为 95 或90 给出最好的结果。但是当要放置的矩形数量非常多时，即使这种方法也很麻烦。这是矩形的排列方式

如果第一个矩形的长度为l，圆的直径为d，则其厚度为sqrt(d2-l2)。如果第二个矩形的长度为k，则其厚度为sqrt(d2-k2)-sqrt(d2 -l2).

有什么算法可以让我去制定结果。

Answer 1

为什么对这个问题进行暴力攻击会很困难？您只需要在计算代码中付出一些努力，我相信它会正常工作。它最多只有 19 个级别。这应该不会太复杂，并且会在……好吧，几个小时内给你结果，正如我刚刚发现的那样。 19 个级别将导致 3.3e17 计算。

关于算法:
对于一个矩形，当矩形为正方形时，您将获得最大的覆盖面积。我认为这很容易理解。正方形的角与圆心成45°(假设水平方向为0°，但实际上无所谓，因为整个结构是点对称的)，大小为(0.707*diameter)^2 = 5000。
最接近宽度 70.7 的是 70。一般来说，我建议检查数字低于 (70) 和高于 (75) 的准确结果 (70.7)。矩形的面积是 70 * 71.41 = 4999。(但很高兴知道，如果高度也必须是 5's-grid 之外的值!)

现在越来越难了，我希望我是对的:
当我写下这个答案时，事实证明我是不对的。 :-( 四舍五入的值比理论最大值的结果更高。但无论如何我都会发布它，也许它有助于找到真正的答案。

当你有 2 个矩形时，要覆盖的最大区域应该是什么时候

• rect1 的角为 30°(以及 150°、210°、330°)，并且
• rect2 的角为 60°(以及 120°、240°、300°)。

尺寸为:

• 矩形 1:0.866*dia * 0.5 *dia = 4330
• 矩形 2:0.5 *dia * 0.866*dia = 4330 - 减去重叠 =>> 0.5*0.36*dia^2 = 1830
• 总和:6160

四舍五入到 5 的网格:

• 矩形 1，#1) 85*52.86 = 4478
• rect 2: #1) 50*(86.60-52.86) = 1696.2 #2) 55*(83.52-52.86) = 1696.1 #3) 45*(89.30-52.86) = 1648

• 求和:6173.87//6173.75//6126

• 矩形 1，#2) 90*43.59 = 3923

• rect 2: #1) 50*(86.60-43.59) = 2151 #2) 55*(83.52-43.59) = 2196 #3) 45*(89.30-43.59) = 2057
• 总和:6074//6119//5980

获胜者是组合 1.1:rect1 = 85，rect2 = 50。

由于使用四舍五入的值，您必须检查每个矩形的上下值(如果它在网格上则准确)值的每个组合，导致最多 3^n 次检查 n 是否为矩形数(n=1 除外)。蛮力并不好，但可能更容易。 (正如上面发现和写的那样，它可能会返回更好的结果，因为这种方法不准确)。

编辑 1:1 个矩形(生成正方形)的公式为:

A = x * sqrt(D²-x²)
calculate the maximum using the derivative of A:
A' = D²-2x² / sqrt(D²-x²) = 0

您也可以在这里找到它:http://oregonstate.edu/instruct/mth251/cq/Stage8/Lesson/rectangle.html

2个矩形的公式是:

A = f(x,y) = x * sqrt(D²-x²) + y * [sqrt(D²-y²)-sqrt(D²-x²)]
( x = width of r1, y = width of r2 )

n 个矩形的公式取决于 n 个未知变量。所以你需要计算n个偏导数。玩得开心! (或者考虑蛮力，因为你已经有了一个网格，不需要进行迭代；-))