БЫТЬ ПРАКТИЧНЫМ
(Распаковка) Алгоритм упаковки (Bin)
Спойлер: просто арендуйте грузовик побольше!
Недавно я столкнулся с практической проблемой: у моей жены была выставка, на которой нужно было перевезти 35+ коробок разного размера по всему штату. Для этого потребуется грузовой фургон/грузовик. Дело в том, что мы хотели, чтобы все эти коробки хорошо помещались в грузовом отсеке, без лишнего «пространства для перемещения», так как искусство было хрупким, и мы не хотели, чтобы оно повредилось при транспортировке.
Алгоритм упаковки в корзину
Как программиста, моим первым побуждением было придумать алгоритм, который рассчитывал бы, поместятся ли все эти ящики в доступное грузовое пространство, и сколько места/объема осталось, поскольку мы не хотели, чтобы их было слишком много.
Алгоритм будет примерно таким:
Для заданного кубовидного контейнера с размерами {l, w, h} определите, может ли заданное количество коробок — также кубоидов с размерами {l, w, h) — поместиться в данный контейнер. Вернуть истину или ложь.
Это займет несколько шагов/функций:
- Проверьте, превышает ли размер самой большой отдельной коробки самый большой размер контейнера (например, может ли поместиться конкретная отдельная коробка)
- Вычислите общий объем контейнера и общий объем всех ящиков. Если объем контейнера меньше объема всех ящиков, понятно - все они не влезут.
- Отсортируйте все коробки по наибольшему измерению (как правило, это должна быть длина)
- Складывайте ящики таким образом, чтобы более тяжелые/большие ящики были внизу и подальше от погрузочной платформы (вы не хотите ее блокировать).
- Добавить один ящик
- Снова пересчитайте доступный объем.
- Найдите следующую коробку, которая могла бы поместиться в доступном пространстве/объеме, особенно в некоторых «карманах», оставшихся от больших коробок.
- Промойте и повторите для дополнительной коробки
- Рассчитать оставшееся пространство после загрузки последней коробки.
- И т.д., и т.д…
Вскоре я понял, что это будет гораздо более сложная задача, чем я себе представлял, и на разработку этого алгоритма уйдет гораздо больше времени, чем он будет стоить для наших практических целей.
Решение
И тут мне пришло в голову: подождите минутку! Существует целая индустрия, занимающаяся судоходством, они наверняка придумали решение этой проблемы. После беглых исследований и некоторых страшных математических определений мы наткнулись на практическое решение — сайт, который дал бы нам именно то, что я стремился создать:
Он даже предлагает пошаговое руководство по упаковке ваших вещей:
Хороший!
У него есть и другие опции, такие как упаковка Multi bin, максимальная загрузка контейнера и т. д. Мы не углублялись в них.
Вывод
После всей этой суматохи мы отказались от этого решения, так как не хотели измерять все коробки :).
В конце концов, может быть, лучший совет - Арендуйте грузовик побольше!
Ваше здоровье!
