nixp.ru v3.0

22 октября 2017,
воскресенье,
22:11:35 MSK

DevOps с компанией «Флант»
anonymous написал 10 марта 2004 года в 01:00 (1749 просмотров) Ведет себя неопределенно; открыл 1814 темы в форуме, оставил 5575 комментариев на сайте.

Мне надо решить задачу — расположить заданные прямоугольники в прямоугольнике с наименьшей площадью. То есть — надо поместить заданные картинки (прямоугольники) в одной, чтобы площадь этой одной была наименьшей.

Алгоритм может быть только приближенный, т.к. оптимальное решение находится только путем перебора всех возможных положений, а их ооочень много. Я думаю, что алгоритм быть должен, но вот куда рыть? Кто-нибудь идею может подсказать?

Я искал в гугле «rectangle filling algorithm» — но ничего не нашел особо, т.к. сформулировать, видимо, нормально не могу. Как получше у гугла спросить?

anonymous

Попробуй «rectangle packing problem»

Good Luck,

UT

anonymous

хм…. Это похоже на олимпиадную задачу по оптимальному заполнению рюкзака фиксированного объема. Решается сие с помощью матрицы размера NxN, где N — общее число картинок.

Оптимальное решение — перебор всех возможных комбинаций….