Упаковка прямоугольников в прямоугольник

[CuteBunny]

Задача: дан прямоугольник с w, h. Его нужно заполнить максимальным кол-вом маленьких прямоугольников из n, с wi, hi, где i >=1 && i <= n, используя все имеющееся пространство, при чем маленькие прямоугольники не должны пересекаться внутри большого.

Как это сделать без трансформаций, без оптимизаций, самым прямым и доступным алгоритмом?

Спасибо.

[Igors]

Здесь трудности с understand'ом

Может быть все таки "куб" с размерами по осям (c, w, h) если у этих размеров 3 и Вы говорите о пространстве?
Если "наибольшим количеством" значит "оптимальное заполнение" то задача выглядит слишком сложной. Наверное речь идет просто о заполнении большого куба непересекающимися кубиками из набора. А уж "наибольшим" или нет - как получится

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

[CuteBunny]

Да мне бы с прямоугольниками разобраться для начала...

[Igors]

Все то же самое, только 2 размера вместо 3

[CuteBunny]

Вроде сделал...

Правда без рекурсий.

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

Не самый наверное все-таки оптимальный вариант, т.к. я два раза делаю полный перебор всех имеющихся прямоугольников, т.е. сложность алгоритма в худшем случае составит O(n^2).

В принципе можно как-то оптимизировать определения подходящего места - не делать весь перебор всех маленьких прямоугольников и проверять на пересечение с новым, но я пока не знаю, как сделать по-другому.

На моей машине прямоугольник 300x300 заполняется рэндомными прямоугольниками ~1с.