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

Ответ 1

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

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

Пусть код функции 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). Теперь мы можем применить memoization, чтобы запустить его вовремя 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. Это связано с тем, что первая десятка отличается от второй десятки. Алгоритм можно фиксировать так, чтобы считать, что оба десятка равны (и, соответственно, ответьте на один), но это немного сложнее.

Ответ 2

Итак, логика заключается в обратном сортировке чисел, и предположим, что список чисел l, а сумма, которая должна быть сформирована, s.

   for i in b:
            if(a(round(n-i,2),b[b.index(i)+1:])):
                r.append(i)    
                return True
        return False

тогда мы пройдем через этот цикл, и число будет выбрано из l по порядку и пусть оно i. существует 2 возможных случая: i является частью суммы или нет. Итак, мы предполагаем, что i является частью решения, а затем проблема сводится к l l[l.index(i+1):] и s si, поэтому, если наша функция является (l, s), то мы называем a(l[l.index(i+1):] ,s-i). и если i не является частью s, тогда нам нужно сформировать список s из l[l.index(i+1):]. Таким образом, это похоже в обоих случаях, только изменение есть, если я является частью s, тогда s = s-i и в противном случае s = s.

теперь, чтобы уменьшить проблему, так что в случае, когда числа в l больше s, мы удаляем их, чтобы уменьшить сложность, пока l не будет пустым, и в этом случае выбранные числа не являются частью нашего решения, и мы возвращаем false,

if(len(b)==0):
    return False    
while(b[0]>n):
    b.remove(b[0])
    if(len(b)==0):
        return False    

и в случае, если l имеет только один элемент слева, либо он может быть частью s, тогда мы возвращаем true, иначе он не возвращается, а цикл будет проходить через другое число.

if(b[0]==n):
    r.append(b[0])
    return True
if(len(b)==1):
    return False

Обратите внимание, что в цикле, если они использовались b..but, это наш список only.and я округлен везде, где это возможно, так что мы не должны ошибаться в результате вычислений с плавающей запятой в python.

r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
    global r
    if(len(b)==0):
        return False    
    while(b[0]>n):
        b.remove(b[0])
        if(len(b)==0):
            return False    
    if(b[0]==n):
        r.append(b[0])
        return True
    if(len(b)==1):
        return False
    for i in b:
        if(a(round(n-i,2),b[b.index(i)+1:])):
            r.append(i)    
            return True
    return False
if(a(sum_to_be_formed,list_of_numbers)):
    print(r)

это решение работает быстро. Быстрее, чем описано выше. Однако это работает только для положительных чисел. Тем не менее, он работает хорошо, если есть решение только в противном случае требуется много времени, чтобы выйти из циклов.

пример выполняется так, как показано ниже:

    l=[1,6,7,8,10]

and s=22 i.e. s=1+6+7+8
so it goes through like this 

1.) [10, 8, 7, 6, 1] 22
i.e. 10  is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8  is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4  
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7  is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6  is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1

просто дать сравнение, которое я запускал на своем компьютере, что не так хорошо. используя

l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]

и

S = 2000

моя петля выполнялась 1018 раз и 31 мс.

и предыдущий цикл кода запустили 3415587 раз и заняли около 16 секунд.

однако в случае, если решение не существует, мой код пробежал более нескольких минут, поэтому я остановил его, а предыдущий код работал около 17 мс, а предыдущий код также работает с отрицательными номерами.

поэтому я могу улучшить некоторые улучшения.

Ответ 3

#!/usr/bin/python2

ylist = [1, 2, 3, 4, 5, 6, 7, 9, 2, 5, 3, -1]
print ylist 
target = int(raw_input("enter the target number")) 
for i in xrange(len(ylist)):
    sno = target-ylist[i]
    for j in xrange(i+1, len(ylist)):
        if ylist[j] == sno:
            print ylist[i], ylist[j]

Этот код python делает то, что вы просили, он будет печатать уникальную пару чисел, сумма которых равна целевой переменной.

if target number is 8, it will print: 
1 7
2 6
3 5
3 5
5 3
6 2
9 -1
5 3

Ответ 4

Я нашел ответ, который имеет сложность времени выполнения O (n) и сложность пространства вокруг O (2n), где n - длина списка.

Ответ удовлетворяет следующим ограничениям:

• Список может содержать дубликаты, например. [1,1,1,2,3], и вы хотите найти пары sum to 2

• Список может содержать как положительные, так и отрицательные целые числа

Код выглядит следующим образом, а затем объясняется:

def countPairs(k, a):
    # List a, sum is k
    temp = dict()
    count = 0
    for iter1 in a:
        temp[iter1] = 0
        temp[k-iter1] = 0
    for iter2 in a:
        temp[iter2] += 1
    for iter3 in list(temp.keys()):
        if iter3 == k / 2 and temp[iter3] > 1:
            count += temp[iter3] * (temp[k-iter3] - 1) / 2
        elif iter3 == k / 2 and temp[iter3] <= 1:
            continue
        else:
            count += temp[iter3] * temp[k-iter3] / 2
    return int(count)

• Создайте пустой словарь, выполните итерацию по списку и поместите все возможные ключи в dict с начальным значением 0. Обратите внимание, что ключ (k-iter1) необходим для указания, например. если список содержит 1, но не содержит 4, а сумма равна 5. Затем, когда мы смотрим на 1, мы хотели бы найти, сколько 4 мы имеем, но если 4 не находится в dict, тогда это вызовет ошибку.
• Повторяйте по списку и подсчитайте, сколько раз происходит каждое целое число, и сохраните результаты в dict.

• Итерации через dict, на этот раз нужно найти, сколько у нас пар. Нам нужно рассмотреть 3 условия:

  3.1 Ключ - это только половина суммы, и этот ключ встречается более одного раза в списке, например. list [1,1,1], сумма равна 2. Мы рассматриваем это особое условие как то, что делает код.

  3.2 Ключ - это только половина суммы, и этот ключ встречается только один раз в списке, мы пропускаем это условие.

  3.3 Для других случаев этот ключ не является половиной суммы, просто умножьте его значение на другое значение ключа, в котором эти два ключа суммируются с заданным значением. Например. Если сумма равна 6, мы умножаем temp [1] и temp [5], temp [2] и temp [4] и т.д. (Я не перечислял случаи, когда числа отрицательные, но идея одинакова.)

Самым сложным шагом является шаг 3, который включает поиск словаря, но при поиске в словаре обычно выполняется быстро, почти постоянная сложность. (Хотя наихудший вариант - O (n), но не должен выполняться для целых ключей.) Таким образом, при условии, что поиск является постоянной сложностью, общая сложность O (n), поскольку мы повторяем только повтор много раз отдельно.

Совет для лучшего решения приветствуется:)