Алгоритм поиска, какое число в списке дает в сумме определенное число

Эта задача сводится к Задаче о рюкзаке 0-1 , где вы пытаетесь найти набор с точной суммой. Решение зависит от ограничений, в общем случае эта задача является NP-полной.

Однако, если максимальная сумма поиска (назовем ее S ) не слишком велика, то вы можете решить проблему с помощью динамического программирования. Я объясню это, используя рекурсивную функцию и мемоизацию , что легче понять, чем подход снизу вверх.

Давайте закодируем функцию f (v, i, S) так, чтобы она возвращала количество подмножеств в v [i:] , которое в сумме равно S . Чтобы решить эту проблему рекурсивно, сначала мы должны проанализировать базу (например: v [i:] пусто):

• S == 0: единственное подмножество [] имеет сумму 0, поэтому это допустимое подмножество. Из-за этого функция должна вернуть 1.

• S! = 0: Поскольку единственное подмножество [] имеет сумму 0, допустимого подмножества нет. Из-за этого функция должна вернуть 0.

Затем давайте проанализируем рекурсивный случай (например: v [i:] не пусто). Есть два варианта: включить число v [i] в текущее подмножество или не включать его. Если мы включаем v [i] , то мы ищем подмножества, которые имеют сумму S - v [i] , в противном случае мы все еще ищем подмножества с суммой S .Функцию f можно реализовать следующим образом:

def f(v, i, S):
  if i >= len(v): return 1 if S == 0 else 0
  count = f(v, i + 1, S)
  count += f(v, i + 1, S - v[i])
  return count

v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))

Проверяя f (v, 0, S)> 0 , вы можете узнать, есть ли решение вашей проблемы. . Однако этот код слишком медленный, каждый рекурсивный вызов порождает два новых вызова, что приводит к алгоритму O (2 ^ n). Теперь мы можем применить мемоизацию , чтобы она работала за время O (n * S), что будет быстрее, если S не слишком большой:

def f(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = f(v, i + 1, S, memo)
    count += f(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))

Теперь можно запрограммируйте функцию g , которая возвращает одно подмножество, которое суммирует S . Для этого достаточно добавлять элементы только в том случае, если есть хотя бы одно решение, включающее их:

def f(v, i, S, memo):
  # ... same as before ...

def g(v, S, memo):
  subset = []
  for i, x in enumerate(v):
    # Check if there is still a solution if we include v[i]
    if f(v, i + 1, S - x, memo) > 0:
      subset.append(x)
      S -= x
  return subset

v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))

Заявление об ограничении ответственности: в этом решении говорится, что есть два подмножества [10, 10], которые составляют 10. Это потому, что оно предполагает, что первая десятка отличается от второй. Алгоритм можно исправить, предполагая, что обе десятки равны (и, таким образом, ответят на единицу), но это немного сложнее.