Как мне упаковать несколько прямоугольников в стиле 2D-коробки?

Question

У меня есть несколько прямоугольников различной ширины и высоты.У меня есть большая прямоугольная платформа, чтобы надеть их.Я хочу упаковать их на одной стороне платформы, чтобы они распространились в продольном (X) измерении, но при этом размер по ширине (Y) был минимальным.То есть разместить их как игру в тетрис.Не может быть совпадений, но могут быть пробелы.Есть ли алгоритм для этого?

Answer 1

Звучит как вариант Упаковка для мусора :

В теории вычислительной сложности, проблема упаковки бункера является комбинаторная NP-сложная задача. В этом, объекты разных объемов должны быть упакованы в конечное количество бункеров емкость V таким образом, чтобы минимизировать количество используемых бункеров.

Есть много вариантов этого проблема, такая как 2D упаковка, линейная упаковка, весовая упаковка, упаковка стоимость и тд. У них много приложения, такие как заполнение контейнеры, погрузка грузовиков с весом емкость, создание резервной копии файла в Съемный носитель и картографирование технологий в FPGA реализация кастома аппаратное обеспечение.

Цитата из той же страницы о возможных решениях:

Поскольку это NP-hard, наиболее эффективные из известных алгоритмов используют эвристика для достижения результатов что, хотя очень хорошо в большинстве случаев, не может быть оптимальным решением. За Например, алгоритм первого соответствия обеспечивает быстрый, но часто неоптимальный решение, предполагающее размещение каждого предмета в первый бен, в котором он будет поместиться. Требуется время log (n log n), где n - количество элементов быть упакованным. Алгоритм можно сделать намного эффективнее при первой сортировке список элементов в порядке убывания порядок (иногда известный как алгоритм уменьшения первого приближения), хотя это не гарантирует оптимальное решение и для более длинных списков может увеличить время работы Алгоритм.

Я предлагаю вам перейти по некоторым ссылкам с этой страницы Википедии. Кроме того, с помощью "алгоритма упаковки мусора" Google вы, вероятно, найдете много соответствующей информации.

Answer 2

Это называется 2D Strip Packing, над которым работал Мартелло. Если вы выполните поиск в Google по их статье, их алгоритм должен быть довольно простым для реализации. Один из способов сделать это - решить вашу проблему с помощью ветвления и привязки. Сначала вычислите жадное решение, чтобы получить максимальную высоту, необходимую вашей упаковке.

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

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