Javascript-форум (https://javascript.ru/forum/)
-   Оффтопик (https://javascript.ru/forum/offtopic/)
-   -   Помогите с поиском решения (https://javascript.ru/forum/offtopic/74591-pomogite-s-poiskom-resheniya.html)

Nexus 23.07.2018 11:20

Помогите с поиском решения
 
Здравствуйте.

Мне нужно найти минимальный трехмерный контейнер для различных предметов, никак не могу найти информации для решения данной задачи.
Задача похожа на задачу об упаковке в контейнеры.

Прошу помощи с поиском решения данной задачи.



UPD.
Дано:
Коллекция объектов: [{width: x, height: y, depth: z}, ...]

Найти:
Размеры максимально малого трехмерного пространства, выраженного кубом либо прямоугольным параллелепипедом, который сможет вместить в себя всю коллекцию объектов.

Объекты можно вращать.

Alexandroppolus 23.07.2018 11:25

Что есть предметы? точки в пространстве, или что-то объемное? Можно ли их двигать, поворачивать, разбирать на детальки?
Контейнер какой? Кирпич, или произвольной формы?
Надо ли сложить в контейнер сразу все предметы, или достаточно уместить только один любой?

MallSerg 23.07.2018 11:31

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

Nexus 23.07.2018 11:39

Alexandroppolus, предметы - трехмерные товары (печатная продукция, книги). Вертеть их можно как угодно, разбирать - нет.
Ограничения по весу отсутствуют.
Контейнер - куб или прямоугольный параллелепипед.

Цитата:

Сообщение от Alexandroppolus
Надо ли сложить в контейнер сразу все предметы, или достаточно уместить только один любой?

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

Nexus 23.07.2018 11:45

MallSerg, в задаче о рюкзаке характеристики контейнера известны.

MallSerg 23.07.2018 12:27

Цитата:

Сообщение от Nexus (Сообщение 490672)
MallSerg, в задаче о рюкзаке характеристики контейнера известны.

А в твоей задаче известны или нет?
Это целое семейство задач и размеры рюкзака далеко не всегда известны.
т.е. Задача сводится к размещению как можно большего числа прямоугольных объектов в заранее известном прямоугольном контейнере
или же Задача разместить заранее известные объекты прямоугольной формы в максимально малом контейнере?
или же объекты не прямоугольной формы?

Nexus 23.07.2018 12:39

Цитата:

Сообщение от MallSerg
А в твоей задаче известны или нет?

Нет, в моей задаче размеры контейнера неизвестны.
Цитата:

Сообщение от MallSerg
Задача разместить заранее известные объекты прямоугольной формы в максимально малом контейнере?

Эта постановка почти подходит к моему случаю, за исключением того, что у меня известные объекты имеют 3 величины (т.е. объекты трехмерные, не двумерные).

MallSerg 23.07.2018 13:11

Цитата:

что у меня известные объекты имеют 3 величины
Не так важно главное что бы прямоугольные это сильно упрощает задачу.
Объекты могут поворачиваться ?
если могут то только на углы кратные 90° или же любые?

Nexus 23.07.2018 13:24

MallSerg, дополнил шапку темы.
Объекты можно вращать как по вертикали, так и по горизонтали.
Если объект (книгу) поворачивать на угол не кратный 90 градусам, то он может деформироваться (потерять товарный вид), поэтому, я думаю,
вращать нужно на угол кратный 90 градусам.

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

MallSerg 23.07.2018 14:28

В общем класс задач задачи упаковки тынц
Можно сразу на пример решения тынц
Задача NP полная простого решения в лоб за разумное время не существует.


Часовой пояс GMT +3, время: 09:07.