 |
|
|
 
|
|
Алгоритм группировки 
| gcc |
|
|||
 Агент алкомафии  Профиль Группа: Участник Сообщений: 2691 Регистрация: 25.4.2008 Где: %&й Репутация: нет Всего: 17 |
есть массив со значениями
[10, 50, 30, 20, 35, 40] есть такая сущность как максимальное значение в одно корзине - пускай это будет 60 мне нужно чтобы все значения сгруппировались жо максимально возможного в корзине чтобы после выполнения алгоритма, было что-то вродебы такого: [ [10,5], [30,20], [35] [40] ] т.е. всего 4 элемента, внутри сгрупировано не более 60 как это сделать? я сходу никак не могу придумать... |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Задача о рюкзаке (точнее, о наполнении одномерных контейнеров). Для ускорения заполняем одну группу (любым методом - ветвей и границ, жадным или ещё как), потом распределяем остаток - правда, при этом не гарантируется минимизация количества групп.
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| gcc |
|
|||
|
Агент алкомафии Профиль Группа: Участник Сообщений: 2691 Регистрация: 25.4.2008 Где: %&й Репутация: нет Всего: 17 |
Akina,
остаток не надо разделять, хочу сделать так как я написал...  спасибо, ищу Добавлено через 2 минуты и 12 секунд
а подскажите, как это называется на английском? я нашел только: http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%...%B2%D0%B5%D0%B9 про Римская католическая церковь Это сообщение отредактировал(а) gcc - 6.6.2011, 17:12 |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Ты не понял... Начало - [10,50,30,20,35,40]. Первая группа - [50,10], остаток - [30,20,35,40]. Вторая группа - [40,20], остаток - [30,35]. Третья группа - [35], остаток - [30]. Четвёртая группа - [30], остатка нет, процесс завершён. Добавлено через 38 секунд Программно - это рекурсия либо псевдорекурсия. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| gcc |
|
|||
|
Агент алкомафии Профиль Группа: Участник Сообщений: 2691 Регистрация: 25.4.2008 Где: %&й Репутация: нет Всего: 17 |
ок, спасибо пробую, просто может быть есть готовое решение, чтобы велосипед не изобретать.... хотел узнать название алгоритма
Это сообщение отредактировал(а) gcc - 6.6.2011, 17:17 |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Метод ветвей и границ.
Жадный алгоритм. И ещё куча всяких разных... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| baldina |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 4 Всего: 101 |
gcc, требуется найти оптимальное решение или любое, удовлетворяющее условию группировки?
оптимальное решение для данной задачи жадным методом не найти |
|||
|
||||
| _Y_ |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
Что-то я не въезжаю. По простоте душевной мне казалось, что жадными называются методы перебирающие (обычно далеко не самым быстрым путем) именно все возможные варианты и, поэтому, гарантированно находящие оптимальное решение. Именно потому они и жадные, что не пропускают ни одного "закоулка". И что недостаток их именно в медленнодействии, а не в неумении найти глобальный оптимум. В чем я ошибаюсь? -------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 4 Всего: 101 |
В этой статье не сказано, какие задачи оптимально решаются жадными методами.
Жадный метод будет оптимален на множестве элементов, образующих матроид. |
|||
|
||||
| esperanto |
|
|||
 Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
На матройдах да, но возмно этим класс не исчерпывается. Что по поводу гридойдов не знаете?
--------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 4 Всего: 101 |
вроде это одно из обобщений матроидов, коих придумали немало. и что?
|
|||
|
||||
| _Y_ |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
Понятно. Жадные они потому, что сразу хотят взять побольше. С терминологией у меня всегда проблемы к сожалению. Кстити, а как тогда называются алгоритмы проверяющие все решения? -------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Полный перебор. Метод ветвей и границ. И так далее...
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| esperanto |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
Вопрос все тот же "Жадный метод будет оптимален ТОЛЬКО на множестве элементов, образующих матроид. ?" --------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0873 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |