| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм группировки |
| Автор: gcc 6.6.2011, 17:03 |
| есть массив со значениями [10, 50, 30, 20, 35, 40] есть такая сущность как максимальное значение в одно корзине - пускай это будет 60 мне нужно чтобы все значения сгруппировались жо максимально возможного в корзине чтобы после выполнения алгоритма, было что-то вродебы такого: [ [10,5], [30,20], [35] [40] ] т.е. всего 4 элемента, внутри сгрупировано не более 60 как это сделать? я сходу никак не могу придумать... |
| Автор: Akina 6.6.2011, 17:11 |
| Задача о рюкзаке (точнее, о наполнении одномерных контейнеров). Для ускорения заполняем одну группу (любым методом - ветвей и границ, жадным или ещё как), потом распределяем остаток - правда, при этом не гарантируется минимизация количества групп. |
| Автор: gcc 6.6.2011, 17:11 | ||
| Akina, остаток не надо разделять, хочу сделать так как я написал...  спасибо, ищу Добавлено через 2 минуты и 12 секунд
а подскажите, как это называется на английском? я нашел только: http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B2%D0%B5%D1%82%D0%B2%D0%B5%D0%B9 про Римская католическая церковь |
| Автор: Akina 6.6.2011, 17:15 | ||
Ты не понял... Начало - [10,50,30,20,35,40]. Первая группа - [50,10], остаток - [30,20,35,40]. Вторая группа - [40,20], остаток - [30,35]. Третья группа - [35], остаток - [30]. Четвёртая группа - [30], остатка нет, процесс завершён. Добавлено через 38 секунд Программно - это рекурсия либо псевдорекурсия. |
| Автор: gcc 6.6.2011, 17:17 |
| ок, спасибо пробую, просто может быть есть готовое решение, чтобы велосипед не изобретать.... хотел узнать название алгоритма |
| Автор: Akina 6.6.2011, 17:38 |
| Метод ветвей и границ. Жадный алгоритм. И ещё куча всяких разных... |
| Автор: baldina 6.6.2011, 18:20 |
| gcc, требуется найти оптимальное решение или любое, удовлетворяющее условию группировки? оптимальное решение для данной задачи жадным методом не найти |
| Автор: _Y_ 6.6.2011, 19:35 | ||
Что-то я не въезжаю. По простоте душевной мне казалось, что жадными называются методы перебирающие (обычно далеко не самым быстрым путем) именно все возможные варианты и, поэтому, гарантированно находящие оптимальное решение. Именно потому они и жадные, что не пропускают ни одного "закоулка". И что недостаток их именно в медленнодействии, а не в неумении найти глобальный оптимум. В чем я ошибаюсь? |
| Автор: Akina 6.6.2011, 21:33 | ||
Во всём. См. напр. http://ru.wikipedia.org/wiki/%D0%96%D0%B0%D0%B4%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC. |
| Автор: baldina 7.6.2011, 13:28 |
| В этой статье не сказано, какие задачи оптимально решаются жадными методами. Жадный метод будет оптимален на множестве элементов, образующих http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4. |
| Автор: esperanto 7.6.2011, 20:48 |
| На матройдах да, но возмно этим класс не исчерпывается. Что по поводу гридойдов не знаете? |
| Автор: baldina 8.6.2011, 00:54 |
| вроде это одно из обобщений матроидов, коих придумали немало. и что? |
| Автор: _Y_ 8.6.2011, 22:25 | ||
Понятно. Жадные они потому, что сразу хотят взять побольше. С терминологией у меня всегда проблемы к сожалению. Кстити, а как тогда называются алгоритмы проверяющие все решения? |
| Автор: Akina 8.6.2011, 23:23 |
| Полный перебор. Метод ветвей и границ. И так далее... |
| Автор: esperanto 9.6.2011, 10:42 | ||
Вопрос все тот же "Жадный метод будет оптимален ТОЛЬКО на множестве элементов, образующих матроид. ?" |
| Автор: baldina 9.6.2011, 15:34 |
| не умничай. ТСу это неинтересно |
| Автор: esperanto 10.6.2011, 12:21 |
| Тсу? Т.е. вы не знаете ответ? |
| Автор: baldina 10.6.2011, 17:05 |
 esperanto, я не собираюсь мериться с Вами ни интеллектом, ни членами. Те боле, что важно не наличие того и другого, а какую пользу приносит их применение. |
| Автор: _Y_ 11.6.2011, 19:16 |
| Akina, а общего названия разве нет? |
| Автор: v2v 29.6.2011, 22:08 | ||
исследование операций |
