将等长矩形放入较大的矩形中

Question

我有一个单独的大矩形dimensions L*W和n smaller rectangles，它们每个都具有相同的尺寸l * w。每个小矩形都有相同的dimensions。

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

如何确定如何缩放较小的矩形以适合全部大矩形？

Answer 1

这里是查找的缩放因子的最大值的算法F使得所有小a x b矩形，由F缩放将适合在含有矩形A x B时：

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

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

   计算f = min(A/(a*p), B/(b*q)).

2. 设F是最大的所有因素f在1

所有对(p, q)的计算来计算可按以下步骤进行：

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

思想的算法的

每对(p, q)表示缩放矩形与水平行中p矩形和q行，最后一个特定布局一个可能不完整。下面是n = 13写成3 * 5 - 2一个例子：

由于p缩放的宽度f*a矩形必须适合的宽度A长方形，我们有：p*f*a <= A或f <= A/(p*a)。同样f <= B/(q*b).因此，此配置的最大比例是min(A/(p*a), B/(q*b)).