Алгоритм оптимальной двумерной компоновки

Question

Есть ли алгоритм Javascript для поиска оптимальных макетов?

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

Мы должны ответить на следующий вид запроса.

Ширина составляет 4000 единиц и требуются следующие формы: 10 лотов 450 x 750, 6 лотов 2500 x 1200 и 5 лотов 900 x 1500. Какова оптимальная компоновка фигур и длина, требуемая для их установки.

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

Answer 1

Есть ли алгоритм Javascript для поиска оптимальных макетов?

Вопрос скорее должен быть «Есть ли (эффективный) алгоритм, доступный как реализация JavaScript». Я лично разместил его на Math SE или на профессиональном сайте Math, вы можете добавить RPP для «Проблемы с прямоугольной упаковкой».

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

Ширина составляет 4000 единиц, а следующие формы необходимы , 10 лотов 450 x 750, 6 лотов 2500 x 1200 и 5 лотов 900 x 1500. Какова оптимальная компоновка формы и длины должны соответствовать их всех.

Существуют ли ограничения на ориентации прямоугольников? (Веселый взгляд here).

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

Таким образом, каждый придерживается эвристики (например, here). Возможно, вы закончите математику уровня исследования, в то время как у меня есть ощущение, что вы ищете оптимизатор «достаточно хорош».