суббота, 19 февраля 2011
13:40

все записи пользователя в сообществе Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Привет. Подскажите, как решать классические задачи на поиск всевозможных комбинаций?
Пример: известен вес определенного кол-ва людей (каждого отдельно) и известна грузоподъемность лифта. Найти группу из максимального кол-ва людей, которых можно за раз перевезти на лифте.
Как такое реализовать? В идеале - на Python. Сама вообще без идей.(

@темы: Алгоритм

URL
Комментарии
19.02.2011 в 13:45

Сортируете массив людей по весу, последовательно берете по одному человеку и если суммарных вес набранных не превышает возможного - берете следующего.
URL
19.02.2011 в 13:49

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Сортируете массив людей по весу, последовательно берете по одному человеку и если суммарных вес набранных не превышает возможного - берете следующего.
На всякий случай добавлю, что сортировать надо по возрастанию и начинать с человека с минимальным весом :)
URL
19.02.2011 в 13:53

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Ох, все гениальное как всегда просто, спасибо большое :)
Просто любопытно, а как это решаемо без сортировки?
URL
19.02.2011 в 13:55

Flex Ferrum
IDDQD - Команда молодости нашей, команда, без которой мне не жить.
Если мне не изменяет память, то такие задачи решаются "жадными" алгоритмами. Предлагаю погуглить на эту тему.
URL
19.02.2011 в 14:00

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Спасибо за наводку. Вышла на "задачу о рюкзаке", кажется, это то, что я ищу.)
URL
19.02.2011 в 14:00

Flex Ferrum
Кстати, наверное, ты прав. Вроде как критерий "каждый раз выбираем локальное оптимальное решение" проходит.
Я, грешным делом, сперва начал думать про динамическое программирование, составил несколько формул и уже потом понял, что ничего этого не нужно)

Просто любопытно, а как это решаемо без сортировки?
Вам на каждом шаге (выборе человека) необходимо выбирать по минимальному весу. Т.е. на каждом шаге в массиве весов нужно находить минимум. Можно и не сортировать тогда.
URL
19.02.2011 в 14:12

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Ния
а чем сортировка не угодила? Быстрая и выбор имеют сложность n * ln n, а если каждый раз искать минимум, то это всего лишь извращение на тему сортировки выбором :) кстати, она очень просто реализуется, буквально в несколько строчек.
И у Вас не совсем задача о рюкзаке, это ее более легкий подвид, который решается при помощи алгоритма, имеющего полиномиальную сложность. Так что не надо из пушки по воробьям :)
URL
19.02.2011 в 14:45

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Да, с сортировкой/минимумом я уже решила, еще раз спасибо.)
Но по-прежнему интересует, как найти всевозможные комбинации. Это вроде экспоненциальная сложность уже будет?
URL
19.02.2011 в 14:54

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Ния
да, эскпоненциальная, только полный перебор вариантов, организовать можно разными способами.
URL
19.02.2011 в 14:59

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
А можно поподробней о способах? :)
URL
19.02.2011 в 15:02

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Ния
поподбробнее уже от конкретной задачи зависит :) и языка тоже. Я питона не знаю. Но в любом случае код не стала бы сюда писать, думайте сами.
URL
19.02.2011 в 15:36

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Да я не прошу код, идеи достаточно.) У меня их ноль.
Всевозможные комбинации из той же группы людей, например.
URL
19.02.2011 в 15:41

Ния
Полный перебор подразумевает, что вы составите все возможные выборки из доступных людей, а потом каждую проверить на "увозимость" лифтом (т.е. общая масса этой выборки должна быть меньше максимально массы лифта).
Вероятно, есть более быстрые решения. Но это уже надо придумывать.
URL
19.02.2011 в 16:01

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Ния
Всевозможные комбинации из той же группы людей, например.
Если нужны все возможные комбинации, то тогда полный перебор. Например, берете одного человека. Это одна комбинация. Потом составляете пары его и всех остальных. Потом для каждой пары подбираете третьего и т.д. Когда закончите с первым человеком, делайте все то же самое, но только совсем не учитывайте первого (иначе будут повторяющиеся комбинации). Здесь удобно использовать рекурсию и парадигму функционального программирования (питон ее вроде как поддерживает).

Хотя я все равно не понимаю, зачем организовывать полный перебор вариантов. Это крайне неэффективно и практически никогда не нужно в реальности, практически всегда достаточно какого-либо приближенного алгоритма (про жадные уже сказали).
URL
19.02.2011 в 16:17

Teen Idle.
Frustrated? Yes. Why? Because it is impossible for me to be God.
Спасибо большое!

А программа с полным перебором нужна для универа, мол, и такое, если что, мы тоже должны уметь.)))
URL
19.02.2011 в 16:34

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Ния
пожалуйста.

Раз для универа и язык Питон, то это наверняка именно на функциональное программирование. Его принципы частично даже противоречат императивному (все приведенные выше способы относились к императивному). Я функциональным не занимаюсь, только немного знаю логическое, язык ПРОЛОГ-Д. В нем не нужно реализовывать полный перебор, это система делает сама. В Питоне, по идее, то же самое, но как именно это работает, я сказать не могу. Читайте книжки, в общем :)
URL