Установка равных прямоугольников в большой прямоугольник

Question

У меня есть один большой прямоугольник dimensions L*W и n smaller rectangles, каждый из которых имеет одинаковый размер l * w. Каждый маленький прямоугольник имеет то же самое dimensions.

Моя цель - разместить все прямоугольники прямоугольника в большом прямоугольнике, делая максимально эффективное использование пространства в большом прямоугольнике. l и w можно масштабировать или уменьшать по мере необходимости, если пропорция сохраняется одинаковой.

Как определить, как следует масштабировать меньшие прямоугольники, чтобы они соответствовали всем их размерам в большом прямоугольнике?

Answer 1

Ниже приведен алгоритм, который находит максимальное значение коэффициента масштабирования F таким образом, что все малые a x b прямоугольников, при масштабировании по F помещаются в содержащей прямоугольник A x B:

1. Для каждой пары (p, q) из положительные целые числа, такие, что

   • p <= n
   • n = p * q - r для некоторого целого r >= 0, удовлетворяющих r < p или p < q

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

2. Пусть F быть максимальным из всех факторов f вычислены в 1.

Вычисление всех пар (p, q) может действовать следующим образом:

1. [Initialize] p := 0
2. [Приращение] p := p + 1
3. [End?] Если 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)).