Задача о рюкзаке

Не подскажите ли следующий алгоритм:
дано n целых ai>0 и целое S>0. Нужно найти подмножество ai, сумме которого равна S или показать, что такого нет.

???

самый простой вариант - это полный перебор.
типа есть у тебя n твоих предметов. ты перебираешь все подмножества из этих предметов и смотришь сумму весов выбранных.
перебор делается очень просто. либо рекурсией, либо берешь строку из n-битов(байтов, слов...) каждый i-ый елемент строки, если ноль, то предмет не взят, если 1, то предмет взят. вот и все.

Сообщение отредактировано: experimenter - 28.04.03, 01:58

полный перебор - едидинственный точный алгоритм решения, насколько я знаю. есть всякие эвристики, но они не всегда решат оптимально... жадный метод, когда берется наибольший предмет, который еще влазит, потом еще и еще тоже , очевидно, не канает.

А разве динамическое решение не пройдет?
Т.е. ставим первый доступный вес, потом смотрим, какие следующие доступные веса и т.д. Должно работать   :

Так это простая задача о рюкзаке. Она решается без перебора. Перебором решается немного другое: n предметов с определенной стоймостью и весом. Выбрать несколько из них так, чтобы их суммарная стоимость была максимальной при заданном весе! Вот это задача о рюкзаке, которая классифицируется как NP-hard  8)

Сообщение отредактировано: tserega - 29.04.03, 10:52

динамическое программирование по-моему тоже самое, что и перебор.

я имел ввиду данный случай.

Цитата tserega, 29.04.03, 14:49:33

А разве динамическое решение не пройдет?
Т.е. ставим первый доступный вес, потом смотрим, какие следующие доступные веса и т.д. Должно работать   :

Так это простая задача о рюкзаке. Она решается без перебора. Перебором решается немного другое: n предметов с определенной стоймостью и весом. Выбрать несколько из них так, чтобы их суммарная стоимость была максимальной при заданном весе! Вот это задача о рюкзаке, которая классифицируется как NP-hard  8)

1) динамическое програмирование подойдет
только то что вы нарисали это жадный алгоритм а не динамический

2) жадный тут не идет он подходит только для непрерывных задач

3) да помоему NP complete a ne hard

Сообщение отредактировано: esperanto - 29.04.03, 14:42

Цитата esperanto, 29.04.03, 18:41:44

1) динамическое програмирование подойдет

как?

Цитата esperanto, 29.04.03, 18:41:44

да помоему NP complete a ne hard

NP-compleate - решаемо без полного перебора (возможно, динамически). Рассматриваемая задача, безусловно, NP-compleate, а с стоимостью предметов - hard.

Цитата Demo_S, 29.04.03, 19:18:23

как?

Если есть веса w1, w2, .. wn, и клетка Can[I] заполнена и следующий возможный предмет j, то и клетка Can[I + wj] тоже должна быть заполнено. Для инициализации
Can[0]:=True; {вес 0 получить можно}
Если надо пролучить и сами номера предметов, то при каждой итерации надо в еще один массив записывать, благодаря какому предыдущему сумарному весу мы получили текущий.

чем данная реализация отличается от перебора?

насколько я понял, также перебираются все комбинации предметов (без учета порядка следования) только решается не для 1 веса, а сразу для всех:)

Отличается тем, что у тебя сложность алгоритма O(n*m), а не что-то типа O(n!)
n - число предметов, m - вес, который надо получить. При больших n динамический метод НАМНОГО лучше.

если правильно делать перебор (исключая перестановки, которые и дают факториал) то будет как раз то же...

Цитата tserega, 30.04.03, 21:38:29

NP-compleate - решаемо без полного перебора (возможно, динамически). Рассматриваемая задача, безусловно, NP-compleate, а с стоимостью предметов - hard.

NP complete это
1)задача класса NP это значит имея решение можно проверить что оно правильно за полиномиальное время
2) любую задачу этого класса можно решить с её помощью и полиноминальной редукцией на нее

Вижу, у вас на форуме упомянули о методе Greedy
Подскажите пожалуйста его формулировку и если можно само описание данного метода

заранее благодарна

uvolga@hotbox.ru

Жадный сетод - на каждом шаге берем то, что на данный момент кажется самым лучшим (для задачи о рюкзаке, например, можно брать предмет, у которго отношение цена/вес будет максимальным)