найти элементы, суммирующие s в массиве

Question

с учетом массива элементов (все элементы являются уникальными), с учетом суммы s найти все подмножества, имеющие сумму s.для бывшего массива {5,9,1,3,4,2,6,7,11,10} сумма равна 10 возможным подмножествам {10}, {6,4}, {7,3}, {5,3,2}, {6,3,1} и т. д. может быть намного больше.также найдите общее количество этих подмножеств.пожалуйста, помогите мне решить эту проблему ..

Answer 1

Это известная проблема возврата, которая может быть решена путем рекурсии. По сути, это метод грубой силы, при котором пробуют каждую возможную комбинацию, но 3 граничных условия, по крайней мере, сокращают поиск.
Вот алгоритм:
Переменная s для суммы выбранных до сих пор элементов.
Переменная r для общей суммы оставшегося массива.
М - необходимая сумма.
k - индекс, начинающийся с 0
w - массив заданных целых чисел

Sum(k,s,r)
{
    x[k]:=1;  //select the current element
    if(s<=M & r>=M-s & w[k]<=M-s)
    then
    {
        if(s+w[k]==M)
        then output all i [1..k] that x[i]=1
        else
        sum(k+1,s+w[k],r-w[k])
    }
    x[k]:=0  //don't select the current element
    if(s<=M) & (r>=M-s) & (w[k]<=M-s)
    then
    {
        if (M==s)
        then output all i [1..k] that x[i]=1
        else
        sum(k+1,s,r-w[k])
    }
}

Я использую массив «x» для обозначения номеров кандидатов, выбранных для решения. На каждом шаге проверяются 3 граничных условия:

1. Sum of selected elements in "x" from "w" shouldn't exceed M. s<M.    
2. Remaining numbers in array should be able to complete M. r>=M-s.
3. Single remaining value in w shouldn't overflow M. w[k]<=M-s.  

Если какое-либо условие не выполнено, это ветвление прекращается.

Answer 2

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

.

>>> import itertools
>>> vals = (5,9,1,3,4,2,6,7,11,10)
>>> combos = itertools.chain(*((x for x in itertools.combinations(vals, i) if sum(x) == 10) for i in xrange(len(vals)+1)))
>>> for c in combos: print c
...
(10,)
(9, 1)
(3, 7)
(4, 6)
(5, 1, 4)
(5, 3, 2)
(1, 3, 6)
(1, 2, 7)
(1, 3, 4, 2)

Что он делает в основном так:

• Для всех возможных размеров подмножества - for i in xrange(len(vals)+1), выполните:
• Перебирать все подмножества с этим размером - for x in itertools.combinations(vals, i)
• Проверка, равна ли сумма значений подмножества 10 - if sum(x) == 10
• В этом случае выведите подмножество

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

Поскольку у вас есть только генератор, а не список, вам нужно подсчитывать элементы при его итерации - или вы можете использовать list(combos), чтобы поместить все значения из генератора в список (это потребляет генератор, поэтому не пытайтесь повторить это до / после этого).

Answer 3

Поскольку вы не говорите, если это домашнее задание или нет, я даю лишь несколько подсказок:

• let nums - массив чисел, который вы можете использовать (в вашем примереnums = {5,9,1,3,4,2,6,7,11,10})

• let targetSum будет суммой, которую вы даете (в вашем примере targetSum = 10)

• sort nums: вы не хотите искать решения, используя элементы nums, которые больше вашего targetSum

• let S_s будет набором целых чисел, взятых из nums, чья сумма равна s

• пусть R_s будет набором всех S_s

• , которые вы хотите найтиR_s (в вашем примере R_10)

• Теперь предположим, что у вас есть функция find(i, s), которая возвращает R_s, используя подмассив nums начальныйиз позиции i

  • если nums[i] > s вы можете остановиться (помните, что вы ранее сортировали nums)

  • если nums[i] == s вы нашли R_s = { { nums[i] } }, поэтому верните его

  • за каждый j in [1 .. nums.length - 1] васхотите вычислить R_s' = find(i + j, targetSum - nums[i]), затем добавьте nums[i] к каждому набору в R_s' и добавьте их к своему результату R_s

• решите вашу проблемупутем реализации find и вызова find(0, 10)

Надеюсь, это поможет