Алгоритм поиска пары сумм из списка чисел?

Ответ 1

В общем случае, когда может быть любое количество элементов, здесь есть алгоритм O (q * log (q)), где q - размер входного списка:

• Сортировка списка q в порядке возрастания.
• Удалите наименьший элемент, m и добавьте его в результирующий набор. Удалите его из q.
• Итерации над q. Сохраните список номеров, которые мы видели. Если мы увидим число (число, которое мы уже видели + m), то отбросим его. Это должно содержать половину чисел (все те, которые не связаны с m).
• Повторяйте с шага 2 до тех пор, пока не будут найдены все номера.

Здесь реализация этого алгоритма в Python:

def solve(q):
    q = sorted(q)
    x = []
    while q:
        x.append(q[0])

        s = [False]*len(q)
        s[0] = True
        j = 1

        for i in range(1, len(q)):
            if q[i] == q[0] + q[j]:
                s[i] = True
                j += 1
                while j < len(q) and s[j]:
                    j += 1

        q = [k for k, v in zip(q, s) if not v]
    return x

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]
from itertools import combinations
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r))
print(solve(q))

Результат:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]

Оригинальный ответ:

Предполагая, что в списке всего 3 числа и что число не может быть отрицательным:

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

Ответ 2

1) Найдите наименьшие два числа, они должны быть частью исходного списка.

2) Найдите их сумму, все меньшее в списке должно быть частью исходного списка.

3) Найдите следующую наименьшую сумму и повторите, пока не будут выполнены все суммы двух чисел.

Каждый раз, когда вы добавляете номер в исходный список или находите сумму, удалите его из большого списка.

4) Продолжайте с 3 суммами и продолжайте увеличиваться до тех пор, пока большой список не станет пустым.

Edit:

Для поиска следующей наименьшей суммы требуется отсортированный список ваших номеров. Если ваш список A, B, C, D, E, то тогда наименьшая сумма равна A + B, а следующая наименьшая сумма равна A + C.

Производительность такая же страшная, как и она: 2 ^ N, но если я правильно читаю ваш вопрос, список содержит ваш исходный список и все возможные суммы, что позволит значительно повысить производительность.

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

Ответ 3

Вот как вы это делаете. Или, по крайней мере, это наивное решение.

Сначала вы заказываете номера в порядке возрастания. Предполагая, что A - это упорядоченный список результатов, а S - множество минимальных чисел, из которых вы можете построить A.

Цикл через A. Хотя не существует подмножества S, которое добавляет до _i, добавляет новый номер в S так, чтобы он выполнял.

На первой итерации это добавит min (A). Второе число, вероятно, будет в S. Это довольно вычислительно интенсивно, потому что для каждого числа, которое вы проверяете в A, вам нужно убедиться, что существует подмножество S, которое добавляет к нему, и что вы не добавляете число который создает подмножество S, которое добавляет что-то в A.

Вы можете оптимизировать это несколько, каждый раз, когда вы добавляете число в S, вы разрабатываете все возможные суммы, включая этот новый элемент, и удаляете их из A. Продолжайте движение до тех пор, пока вы не опустошите A.

Сложно, если числа могут быть отрицательными, но вы увидите это, потому что для этого должен быть отрицательный элемент A.