Общая сумма из набора (логика)

Question

У меня есть логическая проблема для приложения iOS, но я не хочу ее решать с помощью грубой силы.

У меня есть набор целых чисел, значения не являются уникальными:

[3,4,1,7,1,2,5,6,3,4........] 

Как я могу получить подмножество из него с этих 3-х условий:

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

Заранее благодарен!

Answer 1

Это subset sum proble м, это известная проблема NP-Complete, и поэтому нет эффективного (полиномиального) решения.

Однако, если вы имеете дело только с относительно низких чисел - есть псевдо полином времени раствор с помощью Dynamic Programming.

Идея заключается в том, чтобы построить матрицу снизу вверх, который следует за следующие рекуррентные формулы:

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) 

Идея заключается в том, чтобы имитировать перебор - в каждой точке вы «угадать», если выбран элемент или не.

Чтобы получить фактическое подмножество, вам нужно отследить матрицу. Вы итерацию от D(SUM,n), (предполагая, что значение верно) - вы делаете следующее (после того, как матрица уже заполнена):

if D(x-arr[i-1],i-1) == true: 
    add arr[i] to the set 
    modify x <- x - arr[i-1] 
    modify i <- i-1 
else // that means D(x,i-1) must be true 
    just modify i <- i-1 

Чтобы получить случайное подмножество в каждый момент времени, если оба D(x-arr[i-1],i-1) == true и D(x,i-1) == true выбирают случайным образом какой курс действий принять.

Python Code (Если вы не знаете, что 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 

P.S.

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

D(x,i) = 0 x<0 
D(0,i) = 1 
D(x,0) = 0 x != 0 
D(x,i) = D(x,i-1) + D(x-arr[i],i-1) 

И при генерации перестановки, вы делаете ту же логику, но вы решили добавить элемент i вероятности D(x-arr[i],i-1)/D(x,i)