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

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

Спасибо.

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

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

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

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

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

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

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