Какие есть алгоритмы упаковки прямоугольников?

Question

[justslipknot]

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

Comments

[Akina]

Каково соотношение площади поля и суммы площадей плиток? Каков критерий оптимальности упаковки?

Answer 1

[Developer]

Это классическая "задача о рюкзаке" https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
Так же посмотри "2-Dimensional Strip Packing, 2DSP"
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...
https://en.wikipedia.org/wiki/Bin_packing_problem

Comments

[Akina]

Вроде товарищ ничего не говорит о весовых коэффициентах - так что это не рюкзак, а двумерный раскрой.

Answer 2

[Wataru]

Только перебор. Или, если подойдёт достаточно хорошее решение - всякие эвристики с жадностями.

Comments

[Антон Шаманов]

"только перебор" - это вообще в любом случае перебор, брутфорс только если бы в задаче были параллепипеды - коробки

[Wataru]

Антон Шаманов, ну приведите какой-нибудь не переборный алгоритм. Даже двумерный случай упаковки не имеет других решений.

[Антон Шаманов]

Wataru,

это вообще в любом случае перебор

[Wataru]

Антон Шаманов, Я совсем не понимаю, что вы хотите сказать. Сформулируйте, пожалуйста ваше утверждение целиком.

Даже для двумерного случая нужен брутфорс. Возможны всякие оптимизации, типа метода ветвей и границ или различных эвристик. Но это остается таким же экспоненциальным медленным алгоритмом.

[Антон Шаманов]

Wataru,

Или, если подойдёт достаточно хорошее решение - всякие эвристики с жадностями.

нет никакого "или" - есть только перебор с разной степерью эффективности. в некоторых случаях перебирать все варианты не обязательно, достаточно предварительной сортировки, например, у тебя кубики 2х1 и 3х1.