將等長矩形放入較大的矩形中

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)).