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



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

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

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

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

1. на рисунке совсем не оптимальный способ.
2. модули можно поворачивать?
3. я так понял это для газеты?

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

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

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

вот жадный алгоритм (он не всегда оптимален)
1. ищем наибольший (в ширину) модуль среди неиспользованных
2. если таких несколько, выбираем наибольший по высоте
3. пихаем его на страницу в верхний левый угол
4. находим первую неиспользованную ячейку (просмотр слева направо, сверху вниз)
5. если достигли конца страницы, переходим на новую и идем к п.1
6. ищем размеры свободного участка (вниз и вправо)
7. ищем наиболее подходящий по размеру кусок (сначала в ширину, потом в высоту)
8. если куски закончились, идем к п.10
9. если не нашли отмечаем ячейку негодной, идем к п.4
10. все куски расставлены

А какой критерий оптимизации? Максимальная плотность упаковки?

Критерий:
Чтоб площадь пустот (между модулями) был минимальный