делимость частичной суммы и разности целых чисел

Question

Проблема заключается в следующем:

Учитывая набор целых чисел A и другое число k > 1, можно разделить A на два подмножества, сумма которых x и y соответственно, из которых (x - y) mod k = 0

Очевидно, что существует алгоритм определения временной сложности O(2^N), перечисляя все возможные разделы, но есть ли более эффективный? Или это эквивалентно subset sum problem?

Answer 1

Это действительно эквивалентно сумме подмножества и может быть эффективно разрешено (псевдополиномиальное время) с использованием решения DP, так как ваши числа являются целыми числами.

Простое решение к нему с помощью динамического программирования решение о подмножестве суммы:

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

, построив таблицу DP (в восходящем растворе), все, что вам нужно сделать, когда вы сделали это проверьте, есть ли x, что:

D(x,n) = true, abs(x-(SUM-x)) % k = 0 
Where: 
n - number of elements 
SUM = arr[1] + arr[2] + ... + arr[n] 
k - the given integer for mod 
(x-y) % k = (x-(SUM-x)) % k 

---

Однако при малых значениях k, вы можете оптимизировать его, чтобы быть O(n*k) (вместо O(n*SUM). Это все еще псевдополиномиальное время, но может быть огромным улучшением, если k << SUM.

Обратите внимание, что x-y = x-(SUM-x) = 2x-SUM, и вы ищете подмножество, которое суммируется с x таким образом, что 2x - SUM % k = 0.

Простая оптимизация сделать таблицу DP только для размера (k+1) * (n+1) следующим образом:

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

выше верно, потому что (a-b)%k = (a%k - b%k)%k (где% к для отрицательных чисел определяется как complementary modulus

.

Теперь, когда вы закончите настройку своей таблицы, вы можете выполнить поиск, если есть x такой, что ((2x)%k - SUM%k) %k == 0.Это работает, потому что для каждого подмножества, которое составляет t:

(2t - SUM) % k = ((2t)%k - SUM%k) %k = (2(t%k))%k - SUM%k) % k = ((2x)%k - SUM%k) %k