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

[izrukvruki]

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



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

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

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

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

[gamecreator]

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

[izrukvruki]

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

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

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

[gamecreator]

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

[Darth_Beleg]

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

[izrukvruki]

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