Целевая сумма бесконечного потока чисел в python

Question

Я пытаюсь найти целевую сумму из бесконечного потока чисел в Python. Числа положительные (числа> 0), уникальные и неопределенные. Я считаю, что ответом было бы использовать динамическое c программирование или кучу, но не могу понять logi c.

Любая помощь по возможной структуре данных или потоку logi c, чтобы попробовать.

Большое спасибо.

например,

    nums = [ 99,85,1,3,6,72,7,9,22,....]
    targetSum = 27

output: True
Explanation: 1+6+22 = 27(targetSum)

Answer 1

Вы можете использовать набор для отслеживания всех возможных сумм с учетом чисел на данный момент в итерациях. Для каждой итерации добавьте текущее число к каждой существующей сумме в наборе, чтобы добавить к набору, и добавьте само текущее число к набору. Вернуть True, если целевая сумма действительно находится в наборе:

def has_sum(nums, targetSum):
    sums = set()
    for i in nums:
        sums.update([s + i for s in sums if s + i <= targetSum])
        if i <= targetSum:
            sums.add(i)
        if targetSum in sums:
            return True
    return False

, так что:

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)

возвращает True (потому что 1 + 6 + 22 = 29), и что:

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)

возвращает False (потому что ожидаемый результат в вашем вопросе неверен).

Answer 2

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

def has_sum(nums, targetSum):
    if not nums or targetSum <= 0:
        return False
    first, *rest = nums
    return first == targetSum or has_sum(rest, targetSum - first) or has_sum(rest, targetSum)

так, чтобы:

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 29)

возвращало True (потому что 1 + 6 + 22 = 29), и что:

has_sum([99, 85, 1, 3, 6, 72, 7, 9, 22], 27)

возвращает False (поскольку ожидаемый результат в вашем вопросе неверен).

РЕДАКТИРОВАТЬ: Чтобы избежать влияния на производительность копирования входной последовательности минус первый элемент в rest в каждом вызов, приведенный выше код можно улучшить с помощью индекса:

def has_sum(nums, targetSum, index=0):
    if index == len(nums) or targetSum <= 0:
        return False
    num = nums[index]
    return num == targetSum or has_sum(nums, targetSum - num, index + 1) or has_sum(nums, targetSum, index + 1)

Answer 3

@ Pavis,

Одна идея, которую я могу придумать, - использовать плотный график. Вы можете сделать следующее:

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

Я думаю, что этот процесс медленный, tho