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

Question

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

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

-1

algorithm c++subset-sum

Решение

Другие решения

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

Предположим, что:

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

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

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

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

f [x + a_я] = f [x + a_я] || f [x], для каждого x в [M..a_я] — порядок обработки актуален!

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

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

0

Источник

Accepted Answer

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

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)

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

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

Вот код 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

1