Задача об упаковке в контейнеры

[Rock`n`Rolla]

Возникла задача эффективного использования площади. Есть прямоугольная область определенного размера, необходимо на ней разместить прямоугольные объекты наиболее эффективным способом. (Занять по возможности большее кол-во площади).
Например - 7 объектов
X X X
X X X
X

Задано количество объектов (в часности [1..12]), известно соотношение сторон (x/y = 0.9 ), известны максимальная длина и ширина размещаемых объектов.
Дополнительное условие - неполный ряд - внизу

Предпринята попытка что-то сделать но решение не идеально, особенно когда кол-во элементов меньше максимального количества.
http://jsfiddle.net/dj4o6ryv/42/
Непонятно как выбирать размеры размещаемых элементов и как организовать итерации. Надеюсь увидеть более научный подход :)
Заранее спасибо.

[arseniiv]

Объекты нельзя поворачивать, да? Если бы они не были ограничены в размерах, было бы просто.

Rock`n`Rolla в сообщении #916379 писал(а):

Непонятно как выбирать размеры размещаемых элементов и как организовать итерации. Надеюсь увидеть более научный подход :)

Лень копаться в коде на проверку эквивалентности решений, но —

Рассматриваем все возможные конфигурации данного количества объектов с указанными ограничениями. Для каждой легко вычислется соотношение сторон наименьшего описанного прямоугольника, и, соответственно, площадь, занимаемая ею при максимальном растяжении внутри большого прямоугольника. Потом выбирается самая-самая. Тут наверняка можно оптимизировать и не перебирать все — или, может, даже сразу её находить. Ограничение размеров объектов метода не меняет, но на возможности вычислить необходимую конфигурацию может, кажется с первого взгляда, сказаться нехорошо.

Под конфигурациями имею в виду вот такие штучки:

X  XX  XXX  XXXX  XXXXXXX
X  XX  XXX  XXX
X  XX  X
X  X 
X
X
X

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

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Rock`n`Rolla
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.