| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нужен алгоритм поиска оптимального набора слагаемы |
| Автор: neosapient 10.9.2009, 13:05 |
| Здравствуйте. Мне нужен алгоритм, который оптимально быстро найдет слагаемые для получению нужной суммы, либо определит, что данную сумму нельзя получить. Есть массив целых положительных и отрицательных чисел. Нуля быть не может. Сами числа могут повторяться... Например, +1,+1,+1,+7,-4,1000,-996, -3. Найти сочетание слагаемых, чтобы в сумме получить 3. Варианты решения: * 1+1+1 = 3 * 7-4 = 3 * 1000 + 1 +1 -3 -996 = 3 * и т.д. 1) Минимальное условие задачи - найти ХОТЯ БЫ ОДНО сочетание слагаемых, чтобы получить нужную сумму. 2) Оптимально будет, если будут найден вариант(ы) с минимальным числом слагаемых. ============================================================== Сейчас пошел в упор - делаю поиск в глубину, с полным перебором вариантов. Но этот подход плох тем хотя бы по тому, что решения может не быть, а я об этом узнаю, только перебрав все сочетания. Число вариантов возможных комбинаций слагаемых можно рассчитать по формуле (2^n)-1 Таким образом, * для 1 слагаемого - только 1 сочетание * для 2 слагаемых - 3 сочетания * для 3 слагаемых - 7 сочетаний * для 4 слагаемых - 15 сочетаний * для 5 слагаемых - 31 сочетание ......... * для 26 слагаемых - 67108863 сочетания Пример того какие сочетания могут быть. Допустим у меня массив слагаемых из пяти элементов: a, b, c, d, e. Тогда я составляю следующие варианты. a, b, c, d, e, ab, ac, ad, ae, bc, bd, be, cd, ce, de abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde abcd, abce, abde, acde, bcde abcde Итого для пяти слагаемых 31 вариант суммы. Если для 26 элементов, программа слишком долго рассчитывает, то как быть, когда у меня будет 100 элементов? Подскажите оптимальный алгоритм |
| Автор: Akina 10.9.2009, 13:16 |
| Раздели поиск "пополам". Отдельно положительные, отдельно отрицательные. Применительно к исходному посту. Отрицательные составляют разные суммы: -3, -4, -7, -996, -999, -1000, -1003. Соответственно искать надо положительные, образующие одну из сумм: 3, 6, 7, 19, 999, 1992, 1003, 1006. Количество сумм для сочетания 8 элементов (если влоб) = 255. Мы же на первом этапе обработали 7 сочетаний, на втором обработаем ещё 31 сочетание - всего 38. Чем больше набор чисел и чем ближе распределение положительных/отрицательных к 50:50, тем значительнее выигрыш. Правда, тем больше потребуется памяти для массива возможных сумм. |
| Автор: neosapient 10.9.2009, 13:38 |
| Не понял Вас, есть массив слагаемых: +1,+1,+1,+7,-4,1000,-996, -3. Найти сочетание слагаемых, чтобы в сумме получить 3. Варианты решения: * 1+1+1 = 3 * 7-4 = 3 * 1000 + 1 +1 -3 -996 = 3 * и т.д. Вы предлагаете поиск в ширину ? Но он не сможет мне сказать быстро сказать, что нет подходящих комбинаций... |
| Автор: Akina 10.9.2009, 13:49 |
| Задача переборная, куда деваться... максимум что можно сделать - это уменьшить количество переборов. Ещё можно уменьшить это количество, если после деления набора на положительные и отрицательные отсортировать набор положительных элементов и набор искомых сумм - появятся дополнительные отсечения. Скажем, при обработке сумм 3, 6, 7, 19, 999 элемент 1000 можно из рассмотрения смело исключить. |
| Автор: maxdiver 11.9.2009, 10:15 |
| Это задача о рюкзаке, правда, ещё и с отрицательными весами - не совсем стандарт. Для стандартной задачи о рюкзаке есть некий эффективный алгоритм, как раз на только что прошедших олимпиадных сборах в Петрозаводске была задача на это. Чуть позже я найду разбор той задачи, и отпишусь здесь. |
| Автор: maxdiver 14.9.2009, 00:18 |
| Мда, то решение (динамикой) слишком специфичное. Как минимум, наличие отрицательных весов всё портит для него. Так что просто попробуйте поискать алгоритмы по теме "задача о рюкзаке". Из несложных алгоритмов видится только обход в ширину, но судя по всему, он вас не устраивает... |
| Автор: aram90 14.9.2009, 15:42 |
| Отрицательные весы не имеют значиние, важтно диапазон значений. Если числа ограничены, то можно эффективно решить задачу. Алгоритм будет O(n*d), n-количество чисел, d - разность максимально и минимально возможной суммы. |
| Автор: maxdiver 14.9.2009, 20:05 |
| За n*d работает и решение обходом в ширину, разве нет? |
| Автор: aram90 15.9.2009, 18:01 |
| Что значит "обход в ширину", где здесь у нас граф и вершины? |
| Автор: maxdiver 15.9.2009, 23:59 |
| Вершины - это пары (i,sum) (i=0..n, sum=min_possible_sum..max_possible_sum), что означает, что мы просмотрели первые i слагаемых и набрали сумму sum. Рёбра: (i,sum) -> (i+1,sum), (i,sum) -> (i+1,sum+a[i]). Запускаем обход в ширину из состояния (0,0), а потом просто смотрим, какие вершины вида (n,sum) были достигнуты - все они и есть всевозможные суммы, которые можно было набрать. Восстановить сами слагаемые для нужной нам суммы не составит труда. Итого асимптотика O(n*d), т.к. столько вершин и рёбер в графе. Можно даже за ту же асимптотику находить ответы с минимальным числом слагаемых, для этого просто в графе надо ввести веса (на рёбра первого типа поставить вес 0, а второго типа - вес 1). |