Как расположить N прямоугольников, чтобы покрыть минимальную площадь [дубликаты]

Возможный дубликат:

Алгоритм, необходимый для упаковки прямоугольников достаточно оптимальным способом

У меня есть N прямоугольники, каждый из которых имеет произвольный размер рост). Все прямоугольники параллельны X & Оси Y. Я'Я ищу алгоритм, который помогает мне расположить эти прямоугольники бок о бок таким образом, чтобы результирующий ограничивающий прямоугольник имел минимальную площадь, а потенциальные промежутки вокруг / между входными прямоугольниками были как можно меньше. Прямоугольники не могут вращаться и не могут перекрывать друг друга.

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

Например:

+---+   +----------+
| 1 |   |    2     |
+---+   +----------+                 +----------+..           +---+----------+
                                     |    2     |..           | 1 |    2     |
+--------+                ===>       +--------+-+-+    vs     +---+----+-----+
|        |                           |        | 1 |           |        |......
|    3   |                           |    3   +---+           |    3   |......
+--------+                           +--------+....           +--------+......

                                       Unused: 8                 Unused: 18

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

Есть ли алгоритм, который помогает с этим? Я много гуглил, но большинство результатов связано с поиском минимального ограничивающего прямоугольника или с поиском, если N прямоугольников покрывают предварительно определенную область.

Ответы на вопрос(1)

Ваш ответ на вопрос