Вариант суммы подмножества с ненулевой суммой цели

Question

У меня есть массив целых чисел и вам нужно применить вариант subset sum algorithm, за исключением того, что вместо поиска набора целых чисел, сумма которых равна 0, я пытаюсь найти набор целых чисел, сумма которых равна n. Непонятно, как адаптировать один из стандартных алгоритмов суммирования к этому варианту и надеялся на какое-либо понимание проблемы.

Answer 1

Это subset sum problem, который NP-Complete (не известно эффективное решение для NP-полных задач), но если ваши номера относительно небольшие целые числа - существует эффективный псевдо полиномиальное решение ему, что следует повторение:

D(x,i) = false x<0 
D(0,i) = true 
D(x,0) = false x != 0 
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1) 

Позже вам необходимо вернуться к своим выборам, посмотреть, где вы решили «уменьшить» (взять элемент), и где вы решили не «уменьшать» (не принимать элемент), на сгенерированную матрицу ,

This thread и this thread обсудить, как получить элементы для подобных проблем.

Вот код python (взятый из связанного с нитью), который делает трюк.
Если вы не знакомы с python - прочитайте его как псевдокод, это довольно легко понять python !.

arr = [1,2,4,5] 
n = len(arr) 
SUM = 6 
#pre processing: 
D = [[True] * (n+1)] 
for x in range(1,SUM+1): 
    D.append([False]*(n+1)) 
#DP solution to populate D: 
for x in range(1,SUM+1): 
    for i in range(1,n+1): 
     D[x][i] = D[x][i-1] 
     if x >= arr[i-1]: 
      D[x][i] = D[x][i] or D[x-arr[i-1]][i-1] 
print D 

#get a random solution: 

if D[SUM][n] == False: 
    print 'no solution' 
else: 
    sol = [] 
    x = SUM 
    i = n 
    while x != 0: 
     possibleVals = [] 
     if D[x][i-1] == True: 
      possibleVals.append(x) 
     if x >= arr[i-1] and D[x-arr[i-1]][i-1] == True: 
      possibleVals.append(x-arr[i-1]) 
     #by here possibleVals contains 1/2 solutions, depending on how many choices we have. 
     #chose randomly one of them 
     from random import randint 
     r = possibleVals[randint(0,len(possibleVals)-1)] 
     #if decided to add element: 
     if r != x: 
      sol.append(x-r) 
     #modify i and x accordingly 
     x = r 
     i = i-1 
    print sol 

Answer 2

Вы можете решить эту проблему с помощью динамического программирования.

Давайте предположим, что:

• N - это сумма, которая требуется (ваш первый вход).
• M - это количество слагаемых, доступных (ваш второй вход).
• a ... a _M - это сгенерируемые слагаемые.
• f[x] является true, когда вы можете достигнуть суммы в x и false иначе

Теперь решение:

Первоначально f[0] = true и f[1..N] = false - мы можем достичь только сумму нуля без принятия каких-либо слагаемым.

Теперь вы можете перебрать все в _я, где i в [1..m], и с каждым из них выполнить следующую операцию:

F [х + а _я] = F [ x + a _i] || f [x], для каждого x из [M..a _i] - порядок обработки имеет значение!

Наконец, вы выводите f [N].

Это решение имеет сложность O (N * M), поэтому оно не очень полезно, когда вы либо имеете большие входные числа, либо большое количество слагаемых.