Архив форумов ЦИТФорума

[--= Eagle =--]

Дан массив прямоугольников, нужно расположить их в форме прямоугольника с наименьшими возможными сторонами. Будет реализовно на Делфе. Нужен просто алгоритм.
_________________
Информация должна быть общедоступной!

[Andy_user]

Неясны условия:
1. Как задан массив прямоугольников;
2. Разрешается ли прямоугольники поворачивать на 90 градусов;
3. Уточните критерий оптимальности. Может быть наименьший периметр охватывающего примоугольника ?

[GREA]

Очевидно, начинать нужно с квадрата.
Его сторона - корень из суммы площадей.
Сначала пытаемся сложить одну сторону, к ней добавляем другой слой. Все рекурсивно. Если построение не удачно, должны собрать прямоугольник с наименьшей стороной (которая все-таки должа быть больше, чем на предыдущем шаге).
Повторяем процесс, пока не достигнем некого прямоугольника, который и будет минимальным.
Это самый базовый алгоритм.
Задача упрощается, если это похоже на пентамино (то есть, у всех длин сторон всех прямоугольников есть общий НОД)
Действительно, уточни условия и ограничения. Тогда можно будет обьяснить более понятно.

[--= Eagle =--]

Уже уточнил...

1. Масив ректанглов, кол-во и размер задаёт пользователь
2. Конечно, поворачивать можно
3. Да, наименьший периметр охватывающего прямоугольника

2 GREA

А кто сказал, что там будет хоть 1 квадрат?
_________________
Информация должна быть общедоступной!

[GREA]

Я имел в виду то, что сначала, мы должны собирать прямоугольники в один большой КВАДРАТ (пытаемся минимизировать периметр). Если попытка не прошла, ищем суммарный прямоугольник максимально близкий к квадрату (минимальное увеличение одной из сторон). Решаем аналогичную задачу. В случае неудачи, опять увеличиваем сторону и повторяем процесс. Как только смогли собрать прямоугольник, он и будет минимальным (по периметру)