Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 23.07.2018, 12:20
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,008

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

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

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



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

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

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

Последний раз редактировалось Nexus, 23.07.2018 в 13:48.
Ответить с цитированием
  #2 (permalink)  
Старый 23.07.2018, 12:25
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 734

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

Последний раз редактировалось Alexandroppolus, 23.07.2018 в 12:27.
Ответить с цитированием
  #3 (permalink)  
Старый 23.07.2018, 12:31
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 952

Нужна более точная формулировка задачи. Пока звучит как один из видов задачи о рюкзаке на википедии большая статья с вариантами решений некоторых видов задачи о ранце. тынц
Ответить с цитированием
  #4 (permalink)  
Старый 23.07.2018, 12:39
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,008

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

Сообщение от Alexandroppolus
Надо ли сложить в контейнер сразу все предметы, или достаточно уместить только один любой?
Нужно найти минимальные (хотя бы оптимальные, на самом деле) размеры контейнера, способного вместить в себя все предметы.
Ответить с цитированием
  #5 (permalink)  
Старый 23.07.2018, 12:45
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,008

MallSerg, в задаче о рюкзаке характеристики контейнера известны.
Ответить с цитированием
  #6 (permalink)  
Старый 23.07.2018, 13:27
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 952

Сообщение от Nexus Посмотреть сообщение
MallSerg, в задаче о рюкзаке характеристики контейнера известны.
А в твоей задаче известны или нет?
Это целое семейство задач и размеры рюкзака далеко не всегда известны.
т.е. Задача сводится к размещению как можно большего числа прямоугольных объектов в заранее известном прямоугольном контейнере
или же Задача разместить заранее известные объекты прямоугольной формы в максимально малом контейнере?
или же объекты не прямоугольной формы?
Ответить с цитированием
  #7 (permalink)  
Старый 23.07.2018, 13:39
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,008

Сообщение от MallSerg
А в твоей задаче известны или нет?
Нет, в моей задаче размеры контейнера неизвестны.
Сообщение от MallSerg
Задача разместить заранее известные объекты прямоугольной формы в максимально малом контейнере?
Эта постановка почти подходит к моему случаю, за исключением того, что у меня известные объекты имеют 3 величины (т.е. объекты трехмерные, не двумерные).
Ответить с цитированием
  #8 (permalink)  
Старый 23.07.2018, 14:11
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 952

Цитата:
что у меня известные объекты имеют 3 величины
Не так важно главное что бы прямоугольные это сильно упрощает задачу.
Объекты могут поворачиваться ?
если могут то только на углы кратные 90° или же любые?
Ответить с цитированием
  #9 (permalink)  
Старый 23.07.2018, 14:24
Профессор
Отправить личное сообщение для Nexus Посмотреть профиль Найти все сообщения от Nexus
 
Регистрация: 04.12.2012
Сообщений: 3,008

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

Я не прошу готового решения, ссылки на страницу с описанием алгоритма, либо хотя бы названия алгоритма, по которому можно будет найти дополнительную информацию будет достаточно.
Ответить с цитированием
  #10 (permalink)  
Старый 23.07.2018, 15:28
Аватар для MallSerg
Профессор
Отправить личное сообщение для MallSerg Посмотреть профиль Найти все сообщения от MallSerg
 
Регистрация: 07.03.2011
Сообщений: 952

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



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с скриптом для решения по формуле! Evgesha322 Общие вопросы Javascript 6 26.01.2016 16:56
Помогите с поиском тега <a> по всей странице сайта и изменением атрибута! Александр.Воробей Events/DOM/Window 4 03.11.2015 12:23
Помогите с поиском в масиве Eugenee Элементы интерфейса 11 13.10.2014 09:53
Помогите разобраться с поиском berto jQuery 0 22.09.2014 12:26
помогите новичку с поиском! real-man AJAX и COMET 8 12.06.2011 14:07