Нужен алгоритм поиска оптимального набор

[neosapient]

Здравствуйте.
Мне нужен алгоритм, который оптимально быстро найдет слагаемые для получению нужной суммы, либо определит, что данную сумму нельзя получить.

Есть массив целых положительных и отрицательных чисел. Нуля быть не может. Сами числа могут повторяться...
Например, +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 элементов?
Подскажите оптимальный алгоритм

[Igors]

Добрый день

Я помню эту задачу в интерпретации "есть N монеток" Да, перебор, но с "коротким выходом".

1) Добавляете константу ко всем числам и к нужной сумме - делаете все положительным

2) Сортируете числа по возрастанию

3) Перебираете варианты до тех пор пока текущая сумма  не превысит заданную. "Вариант" получаете как комбинацию битов какого-то "большого числа". Пример

Код:

typedef unsigned long long ulong;

int theSum = 345;    // requested sum
int * val = new int[num_val];   

.... // read values

ulong minMask = GetMinMask(theSum, val, num_val);
ulong maxMask = GetMaxMask(theSum, val, num_val);
ulong mask = minMask;

while (mask < maxMask) {
  ++mask;
  ulong mask2 = mask;
  int sum = 0;
  int index = 0;
  while (mask2 && index < num_val) {
    if (mask2 & 1) {
      sum += val[index];
      if (sum >= theSum) {
       if (sum == theSum) {
         // found, save it
       }    
       break;
    }
    ++index;
    mask2 >>= 1;
  }
}

Это будет работать до num_val <= 64. Для больших значений нужно немного повоэиться с простым классом который ведет себя "как двоичное число".

Вычисления GetMinMask и GetMaxMask очевидны

[spectre71]

1) Добавляете константу ко всем числам и к нужной сумме - делаете все положительным

Это не верно, поскольку ты не знаешь кол-во элементов в результатирующей сумме
элементы -2, 3, 5
сумма 3
3=3
-2+5=3

элементы -2+2, 3+2, 5+2
сумма 3+2(+2)?

[Igors]

элементы -2+2, 3+2, 5+2
сумма 3+2(+2)?

Так ведь к сумме тоже добавили 2 и она теперь 5
Вообще этот шаг (сделать все положительным) необязателен. Просто лично мне было бы удобнее считать что все > 0 (интуитивнее)

[spectre71]

Так ведь к сумме тоже добавили 2 и она теперь 5
Вообще этот шаг (сделать все положительным) необязателен. Просто лично мне было бы удобнее считать что все > 0 (интуитивнее)

Будь внимательней
элементы -2+2, 3+2, 5+2 == 0, 5, 7
сумма 3+2 = 5
было 2 варианта - (3) и (-2+5) == 5, стал один (5)==5

Другой пример:
элементы -2, 1, 3, 5
сумма 4
======
элементы -2+2, 1+2, 3+2, 5+2 == 0, 3, 5, 7
сумма 4+2 = 6
Вообще ничего не получишь, хотя было 2 варианта

[Igors]

Вы правы, добавление некорректно 

[ufna]

Просто можно каждый раз, когда сверяемся равно ли это нужной сумме, прибавлять к изначальной сумме сию разницу, помноженную на количество текущее элементов в сумме ))

[spectre71]

Вобще-то экспоненциальный алгоритм это очень плохо.
Данная задача весьма нетривиальная. Надо смотреть в сторону динамического программирования.
А лучше поискать в инете готовые алгоритмы решения данной задачи.

[Igors]

Вобще-то экспоненциальный алгоритм это очень плохо.
Данная задача весьма нетривиальная. Надо смотреть в сторону динамического программирования.
А лучше поискать в инете готовые алгоритмы решения данной задачи.

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

1, 1, 1. .........................1 (очень много единиц)

Да, выходное число всех возможных вариантов может быть огромным. Но ведь никто не обещал что "1" взаимозаменяема  с другой "1" - это и должны быть разные варианты. Давайте считать это одним - и надо делать немного по-другому

[spectre71]

Вот ссылочка
http://ru.wikipedia.org/wiki/Задача_о_ранце

[spectre71]

Вот еще ссылки(Задача о суммах подмножеств)
http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004
http://irodov.nm.ru/cgi-bin/ikonboard/topic.cgi?forum=3&topic=138

[Igors]

Вот ссылочка
http://ru.wikipedia.org/wiki/Задача_о_ранце

Spectre, но ведь человек о (зас)ранце не спрашивал И если он на этот форум подписался - то и погуглить он сам сможет. Ссылка хороша в случае "точного попадания" а иначе..

[spectre71]

Spectre, но ведь человек о (зас)ранце не спрашивал И если он на этот форум подписался - то и погуглить он сам сможет. Ссылка хороша в случае "точного попадания" а иначе..

Не понял смысла твоего ответа, к чему ты это написал?
Это разновидность задачи о ранце, первое что нашел, то и дал.
Человек должен понять что за задачу он решает. Наиболее близка(а скорее всего именно она либо сводится кней) "Псевдополиномиальные алгоритмы/Задача о суммах подмножеств"
http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004

[Igors]

3) Перебираете варианты до тех пор пока текущая сумма  не превысит заданную. "Вариант" получаете как комбинацию битов какого-то "большого числа".

Увы, это неправильно. Пример

Числа: 7, 7, 7, 7, 10
Нужная сумма: 17

Первые три семерки дают 21 т.е. "сумма превысила" и ответ "вариантов нет". Однако он есть (7 + 10)
Я подумаю как правильно 

[Igors]

http://www.2shared.com/file/7739585/779ab827/Sumcpp.html

Получается довольно просто, хотя, конечно "глухой рекурс"