Блог

Основные алгоритмы и реализации упаковки контейнеров можно найти по всему Интернету. Тем не менее, я ищу алгоритм, который будет переупаковывать корзину, используя ограниченное количество временного пространства. Идея заключается в том, что предметы были случайно добавлены в корзину и теперь их необходимо реорганизовать, чтобы свести к минимуму потраченное впустую пространство. Может ли кто-нибудь указать мне на такой алгоритм / реализацию или как начать работу?

ПРАВКА (более подробная информация):

Условные обозначения для изображений:

• Светло-серый = пустое пространство
• Все остальные цвета = прямоугольники для упаковки в корзину

Как упоминал kcsquared, это действительно проблема упаковки прямоугольников. Для того, что я пытаюсь сделать, вращение предметов не допускается.

Вот чего я пытаюсь достичь:

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

Конечный результат будет выглядеть примерно так (без сомнения, это не оптимально, я просто сделал это вручную…):

Однако при перемещении предметов идея заключается в том, что они не могут просто выйти из корзины и отправиться «неизвестно куда». Когда предмет вынимается, он должен идти куда-то еще. Для этой цели у нас есть временное пространство, в которое можно поместить предметы, чтобы освободить место в основной корзине. Это временное пространство меньше, но достаточно велико, чтобы вместить самый большой предмет (и более одного предмета одновременно). Это тоже прямоугольник.

С удовольствием добавлю более подробную информацию или отвечу на любые дополнительные вопросы. Спасибо, что нашли время взглянуть на это!