将相等的矩形拟合成更大的矩形

Question

我有一个大矩形dimensions L*W，并且n smaller rectangles每个矩形都有相同的尺寸l * w。每个小矩形都有相同的dimensions。

我的目标是将所有n of smaller矩形放入大矩形中，同时尽可能最有效地利用大矩形中的空间。l 和 w 可以根据需要放大或缩小，只要比例保持不变即可。

如何确定如何缩放较小的矩形以将它们全部放入大矩形中？

Answer 1

这是一个算法，它找到缩放因子的最大值F，使得所有小a x b矩形在缩放时都F适合包含的矩形A x B：

\n

\n
1. 对于每对(p, q)正整数，使得
\n

\n

\n
• p <= n
\n
• q <= n
\n
• n = p * q - r对于某个整数r >= 0满足r < p或p < q
\n

\n

计算f = min(A/(a*p), B/(b*q)).\n2。让为1 中计算的F所有因子的最大值。f

\n

所有对的计算(p, q)可以如下进行：

\n

\n
1. [初始化]p := 0
\n
2. [增量]p := p + 1
\n
3. [结束？]如果p > n，停止
\n
4. [下一页] 让q := (n + p - 1) / p（整数除法）。下一对(p, q)。\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0
\n
5. [重复]执行2。
\n

\n

算法思想

\n

每对(p, q)代表缩放矩形的特定布局，其中p矩形位于水平行和q行中，最后一个可能不完整。n = 13以下是写为的示例3 * 5 - 2：\n

\n

由于p缩放后的宽度矩形f*a必须适合宽度为 的矩形A，因此我们有：p*f*a <= A或f <= A/(p*a)。相似地f <= B/(q*b).，因此该配置的最大规模是min(A/(p*a), B/(q*b)).

\n