Алгоритм поиска всех различных сумм из списка чисел - PullRequest
Новая
       19

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

0 голосов
/ 09 апреля 2019

Пример ввода: 

4 6 4 3 2 2 1 1

Первое число = Итого, Т (Т <1000) </p>

Второе число = Количество чисел, S (S <= 12) </p>

После S цифр = значения чисел (каждое значение <100). (Повторение может произойти, ввод дается в порядке возрастания) </p>

Моя работа состоит в том, чтобы находить все "различные суммы", используя числа из списка, которые складываются в T.

Итак, пример вывода для этого ввода будет: 

4
3+1
2+2
2+1+1

Я думал о том, чтобы просмотреть список 1 на 1 и найти все комбинации чисел с другим номером, вплоть до размера списка чисел - числа уже оцененных чисел. Вы создаете список из каждой комбинации и добавляете список в HashSet из списков (HashSet для предотвращения дублирования).

Таким образом, вы должны проверить все комбинации 1, 2, 3, 4, 5 и 6, чтобы сначала пойти с 4 Тогда все комбинации 1, 2, 3, 4, 5 размеров идут с 3, игнорируя 4 Тогда все комбинации 1, 2, 3, 4 размера идут с 2, игнорируя 4 и 3

и т.д.

  1. Я не уверен, что этот алгоритм действительно эффективен
  2. Мне нелегко как реализовать этот алгоритм. Я не могу обернуть голову, как зациклить структуру, чтобы получить желаемые комбинации.

Ответы [ 2 ]

1 голос
/ 09 апреля 2019

Вы должны попробовать рекурсивное решение.В основном вам нужно работать с идеей, что для каждого номера вы можете включить его в свою сумму или нет.Это означает, что вы строите набор мощности своих чисел и получите решение O(2^N).

Кратко в псевдокоде: 

def get_all_sums(arr, target):

    result = []

    def helper(index, current_arr, current_sum):

        # once you've gone over the arr you can return. If all your numbers are positive
        # you can also return early if the current_sum > target
        if index == len(arr): return

        # solution found - add it to the result
        if current_sum == target: result.append(current_arr)

        # include the current index
        helper(index + 1, current_arr + [arr[index]], current_sum + arr[index])

        # don't include the current index
        helper(index + 1, current_arr, current_sum)

    helper(0, [], 0)

    # sort and hash to get rid of duplicates; return a set
    return {tuple(sorted(i) for i in result)}
0 голосов
/ 10 апреля 2019

Ответ можно найти с помощью простой рекурсии, которую я продемонстрирую на примере из вопроса.

На первом уровне рекурсии решаемая проблема: 

target=4 count=6 allowed={4,3,2,2,1,1} chosen={}

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

target=0 size=5 allowed={3,2,2,1,1} chosen={4}
target=1 size=4 allowed={2,2,1,1} chosen={3}
target=2 size=3 allowed={2,1,1} chosen={2}
target=3 size=1 allowed={1} chosen={1}

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

На втором уровне рекурсии, когда параметры 

target=0 size=5 allowed={3,2,2,1,1} chosen={4}

Это успешный базовый случай: target равен 0. В этом случае добавляет {4} в список вывода , поскольку это решение.

На втором уровне рекурсии, когда параметры 

target=1 size=4 allowed={2,2,1,1} chosen={3}

Код должен пропускать 2, так как 2 больше, чем цель.Таким образом, единственный рекурсивный вызов - 

target=0 size=1 allowed={1} chosen={3,1}

Это опять-таки базовый случай, поэтому третий уровень рекурсии добавит {3,1} к выводу .

На втором уровне рекурсии, когда параметры 

target=2 size=3 allowed={2,1,1} chosen={2}

, будет два рекурсивных вызова 

target=0 size=2 allowed={1,1} chosen={2,2}
target=1 size=1 allowed={1} chosen={2,1}

Первый из них - базовый случай, поэтому добавить {2,2} к выводу .Другой рекурсивный вызов в конечном итоге добавит {2,1,1} к выводу .

На втором уровне рекурсии, когда параметры 

target=3 size=1 allowed={1} chosen={1}

есть один рекурсивный вызов 

target=2 size=0 allowed={} chosen={1,1}

Это базовый случай сбоя: target не равен нулю, а size равен 0.

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

Также обратите внимание, что максимальная глубина рекурсии определяется S, поэтому важно, чтобы S былоограничено относительно небольшим числом (S <= 12 квалифицируется как достаточно маленькое).

...