Есть 5 прямоугольников (A B C D E), расположенных на полскости, необходимо подобрать увеличить/уменьшить их так, чтобы они полность занимали определенную площадь (см. рисунок). Высоту и ширину можно менять в любую сторону, главное чтобы сохранялись пропорции прямоугольников. Подскажите алгоритм, как это расставить, или хотя бы в каком направлении двигаться.


Это сообщение отредактировал(а) vivalaakam - 3.10.2013, 08:58

Наверное ест' готовые алгоритмы, которых я не знаю. Если же лепит' самому, я бы начал скрещиват' алгоритм заполнения рюкзака с каким-либо алгоритмом случайной мутации размеров прямоугол'ников. Т.к прямоугол'ников мало, можно даже и обычный Монте-Карло; ну а хочется покрасивее - генетический алгоритм какой. 

В целом промерно так:
1. Выбираем исходные размеры прямоугол'ников случайно или еще как. Но так, чтобы всe поместилис', хот' и с запасом.
2. Заполняем рюкзак.
4. Генетическими мутациями улучшаем заполнение, мутируя как размеры, так и последовател'ност' расположения. Упаковку каждого потомка делаем пакуя рюкзак. Критерий - наимен'шая незаполненная площад'. Потомки, не помещающиеся в рюкзак считаются метрворожденными.

Наворочено, конечно, зато прикол'но  

_Y_, Заполнение рюкзака - не сюда. Тут можно свободно менять размеры, а все алгоритмы заполнения первым делом сортируют по размерам объектов ;)

vivalaakam, 
Вероятно, решить можно перебором. Перебирать нужно "топологически" одинаковые  "картинки расположения" объектов. По каждой такой картинке можно состряпать систему уравнений, в которую можно подставить имеющиеся размеры картинок и получить решение или его отсутствие. Для каждой картинки нужно перебирать перестановки всех объектов. 

Например для имеющейся в первом посте картинки, получим такую систему уравнений (Первая буква переменой - имя объекта, вторые: k - коэффициент уменьшения, h- высота, w - ширина. 0 - рамка габаритного размера):
-- Ak*Aw+Bk*Bw=0w
-- Ak*Aw+Ck*Cw+Ek*Ew=0w
-- Dk*Dw+Ek*Ew=0w
-- Ak*Ah+Dk*Dh=0h
-- Bk*Bh+Ck*Ch+Dk*Dh=0h
-- Bk*Bh+Ek*Eh=0h

6 уравнений - 5 неизвестных. Задача может не иметь решения. 

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

Ну так и ладно. Генетическому алгоритму и проще. Пусть мутирует только размер объектов, а их расположение определяется рюкзаком.

ЗЫ: Я не настаиваю на оптимальности моего решения. Даже наоборот. Просто пришло в голову и наверняка будет работать.