Алгоритм расчет минимального объема

Question

[S0mnium]

Хабровчане подскажите алгоритм расчета минимального объема упаковки с учетом, что у меня n предметов разного объема.

Comments

[S0mnium]

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

Answer 1

[DeVitoz]

Вообще минимальный объем упаковки равен сумме объемов предметов, которых нужно поместить в упаковку )) Контекста задачи то нет. Либо вам нужно рассчитать длину, ширину и высоту упаковки, в которую уместились бы все предметы. Скорее всего это и есть задача. Поясните

Comments

[S0mnium]

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

[DeVitoz]

Это рассматривали?

[S0mnium]

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

[DeVitoz]

А предметы прямоугольные парралелепипеды или как тетрисе разной формы?

[S0mnium]

На текущий момент взял у ребенка несколько параллелепипедов разного размера

Answer 2

[Vladimir F]

Думаю будет интересно habrahabr.ru/post/136225/

Comments

[S0mnium]

Смотрел, но у меня посложнее вариант будет 3D. И конечного результата объема я заранее не знаю.

Answer 3

[m08pvv]

ru.wikipedia.org/wiki/Задача_об_упаковке_в_контейнеры
Ну или начать с объёма, равного сумме и пытаться уложить пока не уложится, увеличивая объём.

Comments

[S0mnium]

Смотрел задачку любопытная, но нацелена на равное распределение по контейнерам. Тут задача высчитать оптимальный объем укладки.

[m08pvv]

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

[S0mnium]

Необходимо несколько коробок с разным размером уложить в одну (размер которой надо вычислить), желательно максимально с минимальным объемом. Размер исходных коробок может варьироваться.
Есть мысли решения через расчет по площадям сторон как в habrahabr.ru/post/136225/, но опять таки не известно как будет это смотреться с другого бока.
Расчет по объемам не даст необходимого результата. Перебором конечно можно но при увеличении вложенных коробок будет очень долго.
Вот и поставлен вопрос с точки зрения того, что может кому-то приходилось решать подобную задачу. Или хотя бы «пнули» в нужную сторону.

[m08pvv]

stackoverflow.com/questions/6988300/fill-volume-algorithm

[m08pvv]

http://www.mpi-inf.mpg.de/~vanstee/packing-j.pdf

Answer 4

[DeVitoz]

А форма, размеры стороны упаковки имеют значение или могут быть произвольные?

Comments

[S0mnium]

Форма прямоугольник и уложить надо в прямоугольник, стороны абсолютно разные у всех.

Answer 5

[hasu0]

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

Comments

[S0mnium]

Спасибо, буду думать, может в голову что придет, реализовывал подобное года 3-и назад, исходников не сохранилось, но там был перебор простой и предметов для укладки боле не более 3-х

Answer 6

[Agapkin]

Подскажите, решили вопрос? Если да, то как? Столкнулись сейчас с такой же задачей.