Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Размещение коробок в паралелепипеде. Зазмещение коробок в транспорте. 
:(
    Опции темы
MashovetsAnton
Дата 19.6.2008, 08:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 19.6.2008

Репутация: нет
Всего: нет



Вот задача: Есть N коробок, есть размеры (ширина, высота, длина) есть парамелипипед с размерами (ширина, высота, длина) как узнать сколько поместиться коробок в данный парралелипипед?  Тупо по объему не получиться.... Надо как-то размещать коробки. Встачал сдесь алгоритм размещения прямоугольников на плоскости. Что-то пододное надо...
Помогите пожалуйста... Буду всем благодарен...

PM MAIL   Вверх
ksili
Дата 19.6.2008, 10:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 2
Всего: 17



Известных универсальных алгоритмов нет. Насколько я знаю, эта задача обладает экспоненциальной сложностью (т.е. чтобы найти оптимальный вариант, надо перебрать все комбинации)
Кто-нибудь если разрабатывает алгоритм, полноценно решающий задачу, то не открывает его. Например, вот эти ребята http://www.packer3d.ru/
Там же малость про алгоритм


--------------------
Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)
PM MAIL   Вверх
SoWa
Дата 20.6.2008, 14:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74



Да в принципе можно и самому придумать оптимизации. Но все-же без перебора всех вариантов не обойтись


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
Akina
Дата 20.6.2008, 16:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



Поиск по Инету по теме "Задача о рюкзаке", трехмерный вариант.
Ссылок - ну просто море.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
ksili
Дата 21.6.2008, 12:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 2
Всего: 17



SoWa, по-моему "оптимизация" и "перебор всех вариантов" - это как раз почти противоположные пути. Оптимизация такого алгоритма наверное в том и заключается, что отбрасываются заведомо неоптимальные расстановки, и за счёт этого время перебора сокращается.
Цитата(Akina @  20.6.2008,  20:55 Найти цитируемый пост)
Поиск по Инету по теме "Задача о рюкзаке", трехмерный вариант.Ссылок - ну просто море.

Там кажется все только для общего развития. Можно от того, что найдете в инете, как-то оттолкнуться, чтобы начать самому решать эту задачу. Готовых решений никто не выложит. Да и вообще, я в основном находил мат. выкладки для решения двухмерного варианта этой задачи.


--------------------
Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)
PM MAIL   Вверх
SoWa
Дата 22.6.2008, 19:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Харекришна
****


Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74



Цитата(ksili @  21.6.2008,  12:40 Найти цитируемый пост)
SoWa, по-моему "оптимизация" и "перебор всех вариантов" - это как раз почти противоположные пути. Оптимизация такого алгоритма наверное в том и заключается, что отбрасываются заведомо неоптимальные расстановки, и за счёт этого время перебора сокращается.

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




Я все-еще пьяный )))))) 3:1 !!!!!!


--------------------
Всем добра smile
PM MAIL ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0757 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.