Замостить страницу, нужен алгоритм Опции

[izrukvruki]

Задача такая (очень мне актуальная):



А=2 см.
Есть страница, размер 12А на 18А (24 на 36 см), разбитая на ячейки размером 2А на А (4 см на 2 см) - обозначена серым пунктиром

Есть массив модулей (прямоугольников) размера кратного 2А. Например: два черных, голубой, малиновый, красный, зеленый, оранжевый...

Нужен алгоритм:
Как замостить страницу этими модулями? Оптимально не обязательно, но как можно рациональнее. Общая площадь модулей может быть больше площади страницы, тогда расставить сколько влезет и произвести переход на следующую страницу.

Например оранжевый модуль можно разместить как он сейчас расположен, но лучше его впихнуть в место обозначенное стрелочкой...

[izrukvruki]

Я ж говорю абсолютно оптимальный не надо, но и в тоже время и один модуль на страницу - тоже не подойдет.
Поворачивать нельзя.
Правильно понимаешь!!!

У меня есть такое соображение:
страница это массив из ячеек a(i,j). Если ячейка = 0 то ячейка свободна, если 1 то занята. Берем первый модуль и идем по массиву, в поисках свободной ячейки, если нашли, то проверяем чтоб необходимые для модуля ячейки (вправо и внизу) были тоже свободны, если таких ячеек не нашлось переходим на вторую страницу и повторяем операцию, до тех пор пока не разместим модуль. Далее берем второй модуль и возвращаемся на первую страницу и запускаем алгоритм.

Неоптимальность возникает из-за того что берем модули последовательно. Наверное есть ситуации, когда другая очередность взятия модулей даст более рациональную замостку страницу... но повторяю, что оптимальность не требуется...