SilenceOfWinter
@SilenceOfWinter
та еще зажигалка...

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

У товаров заданы ширина\длина\высота, как вычислить оптимальный (т.е. наиболее компактный) размер посылки?
  • Вопрос задан
  • 1340 просмотров
Решения вопроса 1
zoonman
@zoonman
⋆⋆⋆⋆⋆
Почитайте тут engsi.ru/doc/781936.html
Эта задача из разряда труднорешаемых, поэтому в большинстве случаев идеальных решений нет.

Т.к. вам нужно решать задачу для интернет-магазина, то в большинстве случаев достаточно грубой оценки.
Обычно люди покупают относительно немного вещей (до 10), поэтому можно поступить методом тетриса в один слой.
Отсортируете посылки по длине. Получите сумму длин. Возьмите 1/3 от суммарной длины, начните выкладывать посылки по длине. Если одна вышла за 1/3 длины, увеличьте длину до последней посылки.
Все, вы получили дно тетриса. Дальше просто кладите слоями по максимальной ширине.
В итоге у вас получится большая плоская коробка с максимальной высотой товара.
Это простое неоптимально решение, но оно будет работать быстро, что важно для интернет-магазина.
Переплату за доставку можно возращать ввиде кредита покупателю на следующую покупку.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Попарно убираем товары с одной площадью в основании (так, чтобы одна из сторон была равна или меньше, но минимум разницы) и дающие в сумме нужную высоту блока размещения. Начинаем без пары с самого габаритного.
Как будет готово - размещаем площади оснований на заданной плоскости тем же методом.
Блоки размещения - можно также комбинировать той же схемой алгоритма, начиная с самого габаритного.
Товары и блоки размещения - можно крутить во все стороны.
UPD:
Изначально - нужно определиться с размерами одной из сторон посылки: пропорции размеров или чётко заданные размеры, чтобы можно было определить оптимальный размер начального блока размещения.
Или должны быть заранее известны условия компактности:
1. минимально занимаемый объём пространства без ограничений на любой из размеров
2. минимальное удаление углов параллелепипеда от центра фигуры, т.е. идеальный вариант - куб.
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
Упаковка параллелепипедов. NP-полная задача, точное решение — перебор. Сам решал упаковку прямоугольников (т.е. в 2D) генетическим алгоритмом с переменным успехом.
Скорее всего, у вашей службы доставки есть ящики стандартного размера — потому стоило бы приспосабливаться к этим ящикам.
Ответ написан
@polifill
НИКАК.
Если бы упаковка была универсального размера, учитывающего все впадины и выпуклости.....

А по факту упаковка - стандартна (ну или выбор из нескольких)
Максимум что можно - попытаться подогнать под ближайшую бОльшую коробку.
Ответ написан
Комментировать
@Tereverda
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы