Как рассчитать размер посылки?

Question

[Миша Васильев]

Всем привет!

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

Я так понимаю, что чем более ящик похож на куб, тем лучше.

Answer 1

[Александр Кубинцев]

Это задача о ранце, есть много алгоритмов. Гуглите.

Comments

[Миша Васильев]

В задаче о ранцах габариты ранца известны.

[Андрей]

Если габариты ранца у Вас изменяемы, то что есть целевая функция ? Минимум объема коробки ?

[Миша Васильев]

@OLS в идеале -- минимум площади поверхности (именно это я имел ввиду, когда писал, что "Я так понимаю, что чем более ящик похож на куб, тем лучше", но я не настоящий сварщик и математик из меня не очень). Я нагуглил много чего интересного про NP-полные задачи, экспоненциально возрастающую сложность и т. д. Я знаю, например, что какие-то сложные задачи часто решаются с приемлимой (низкой?) точностью на основе каких-то алгоритмов, которые более менее доступны для понимания средних умов (меня). Может быть и для такой задачи есть такой подход, подумал я, и написал на тостер.

[Андрей]

@vasilyev , может у Вас всего 10-20 объектов и задача решается динамическим программированием ?

[Миша Васильев]

@OLS у меня покупки интернет-магазина, если уж быть точным. Их немного, да. Редко больше 10. И расчет носит примерный характер. Проблема в том, что у меня нет размеров контейнера. Если бы были -- я бы решал задачу по слоям, получил бы устраивающую меня точность, наверное.

[Пума Тайланд]

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

[Пума Тайланд]

а алгоритм будет вообще как в начальной школе.

[Миша Васильев]

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

[Пума Тайланд]

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

[Миша Васильев]

@opium понял, так можно, да. Спасибо!

Answer 2

[Андрей]

Задача NP-сложная, весь мир сражается за эвристики :
www.kaggle.com/c/packing-santas-sleigh
(очень советую в плане идей и вариантов - форум к этому соревнованию (слева ссылка))

Comments

[Миша Васильев]

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

[Андрей]

Тогда попробуйте генетические алгоритмы

[Миша Васильев]

@OLS ох, я все четче понимаю, что не моего поля задача. :-) Спасибо за помощь. :-)