Блог

недавно я заинтересовался проблемой с суммой подмножества, которая заключается в нахождении подмножества с нулевой суммой в надмножестве. Я нашел несколько решений на SO, кроме того, я наткнулся на конкретное решение, которое использует подход динамического программирования. Я перевел его решение на python на основе его качественных описаний. Я пытаюсь оптимизировать это для больших списков, которые занимают много моей памяти. Может кто-нибудь порекомендовать оптимизации или другие методы для решения этой конкретной проблемы? Вот моя попытка на python:

 import random
from time import time
from itertools import product

time0 = time()

# create a zero matrix of size a (row), b(col)
def create_zero_matrix(a,b):
    return [[0]*b for x in xrange(a)]

# generate a list of size num with random integers with an upper and lower bound
def random_ints(num, lower=-1000, upper=1000):
    return [random.randrange(lower,upper 1) for i in range(num)]

# split a list up into N and P where N be the sum of the negative values and P the sum of the positive values.
# 0 does not count because of additive identity
def split_sum(A):
    N_list = []
    P_list = []
    for x in A:
        if x < 0:
            N_list.append(x)
        elif x > 0:
            P_list.append(x)
    return [sum(N_list), sum(P_list)]

# since the column indexes are in the range from 0 to P - N
# we would like to retrieve them based on the index in the range N to P
# n := row, m := col
def get_element(table, n, m, N):
    if n < 0:
        return 0
    try:
        return table[n][m - N]
    except:
        return 0

# same definition as above
def set_element(table, n, m, N, value):
    table[n][m - N] = value

# input array
#A = [1, -3, 2, 4]
A = random_ints(200)

[N, P] = split_sum(A)

# create a zero matrix of size m (row) by n (col)
#
# m := the number of elements in A
# n := P - N   1 (by definition N <= s <= P)
#
# each element in the matrix will be a value of either 0 (false) or 1 (true)
m = len(A)
n = P - N   1;
table = create_zero_matrix(m, n)

# set first element in index (0, A[0]) to be true
# Definition: Q(1,s) := (x1 == s). Note that index starts at 0 instead of 1.
set_element(table, 0, A[0], N, 1)

# iterate through each table element
#for i in xrange(1, m): #row
#    for s in xrange(N, P   1): #col
for i, s in product(xrange(1, m), xrange(N, P   1)):
    if get_element(table, i - 1, s, N) or A[i] == s or get_element(table, i - 1, s - A[i], N):
        #set_element(table, i, s, N, 1)
        table[i][s - N] = 1

# find zero-sum subset solution
s = 0
solution = []
for i in reversed(xrange(0, m)):
    if get_element(table, i - 1, s, N) == 0 and get_element(table, i, s, N) == 1:
        s = s - A[i]
        solution.append(A[i])

print "Solution: ",solution

time1 = time()

print "Time execution: ", time1 - time0
  

Я не совсем уверен, является ли ваше решение точным или PTA (многовременное приближение).

Но, как кто-то указал, эта проблема действительно NP-полная.

Это означает, что каждый известный (точный) алгоритм имеет экспоненциальное поведение во времени в зависимости от размера входных данных.

Это означает, что если вы можете обработать 1 операцию за 0,01 наносекунды, то для списка из 59 элементов потребуется:

 2^59 ops -->     2^59     seconds -->     2^26      years -->      1 year
            --------------           ---------------
            10.000.000.000           3600 x 24 x 365
  

Вы можете найти эвристические методы, которые дают вам всего лишь ШАНС найти точное решение за полиномиальное время.

С другой стороны, если вы ограничиваете задачу (другой), используя границы для значений чисел в наборе, тогда сложность задачи уменьшается до полиномиального времени. Но даже тогда потребляемое пространство памяти будет многочленом ОЧЕНЬ высокого порядка.
Потребляемая память будет намного больше, чем несколько гигабайт, которые у вас есть в памяти. И даже намного больше, чем несколько тера-байт на вашем жестком диске.

( Это для небольших значений границы для значения элементов в наборе)

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

Мне показалось, что вы использовали ограничение 1000 при построении вашей матрицы инициализации.

Вы можете попробовать меньшую границу. То есть … если ваш ввод последовательно состоит из небольших значений.

Удачи!

Кто-то в Hacker News предложил следующее решение проблемы, которое мне очень понравилось. Это просто происходит на python :):

 def subset_summing_to_zero (activities):
  subsets = {0: []}
  for (activity, cost) in activities.iteritems():
      old_subsets = subsets
      subsets = {}
      for (prev_sum, subset) in old_subsets.iteritems():
          subsets[prev_sum] = subset
          new_sum = prev_sum   cost
          new_subset = subset   [activity]
          if 0 == new_sum:
              new_subset.sort()
              return new_subset
          else:
              subsets[new_sum] = new_subset
  return []
  

Я потратил на это несколько минут, и это сработало очень хорошо.

Интересная статья об оптимизации кода на Python доступна здесь. По сути, основной результат заключается в том, что вы должны встроить свои частые циклы, поэтому в вашем случае это означало бы вместо того, чтобы вызывать get_element дважды за цикл, помещать фактический код этой функции внутри цикла, чтобы избежать накладных расходов на вызов функции.

Надеюсь, это поможет! Приветствия

первый бросающийся в глаза

 def split_sum(A):
  N_list = 0
  P_list = 0
  for x in A:
    if x < 0:
        N_list =x
    elif x > 0:
        P_list =x
  return [N_list, P_list]
  

Несколько советов:

1. Попробуйте использовать одномерный список и использовать bitarray, чтобы как минимум уменьшить объем памяти (http://pypi.python.org/pypi/bitarray ) таким образом, вы просто измените функцию get / set. Это должно уменьшить объем вашей памяти как минимум на 64 (целое число в списке является указателем на тип integer whit, поэтому оно может быть в 3 раза * 32)

2. Избегайте использования try — catch, но сначала определите правильные диапазоны, возможно, вы обнаружите, что получите огромную скорость.

Следующий код работает для Python 3.3 , я использовал модуль itertools на Python, в котором есть несколько отличных методов для использования.

 from itertools import chain, combinations
def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) 1))


nums = input("Enter the Elements").strip().split()
inputSum = int(input("Enter the Sum You want"))

for i, combo in enumerate(powerset(nums), 1):
    sum = 0
    for num in combo:
        sum  = int(num)
    if sum == inputSum:
        print(combo)
  

Ввод-вывод выглядит следующим образом:

 Enter the Elements 1 2 3 4
Enter the Sum You want 5
('1', '4')
('2', '3')  

Просто измените значения в вашем наборе w и, соответственно, сделайте массив x таким же большим, как len из w, затем передайте последнее значение в функцию subsetsum как сумму, для которой вам нужны подмножества, и все будет сделано (если вы хотите проверить, указав свои собственные значения).

 def subsetsum(cs,k,r,x,w,d):
    x[k]=1
    if(cs w[k]==d):
        for i in range(0,k 1):

            if x[i]==1:
                print (w[i],end=" ")
        print()

    elif cs w[k] w[k 1]<=d :
        subsetsum(cs w[k],k 1,r-w[k],x,w,d)

    if((cs  r-w[k]>=d) and (cs w[k]<=d)) :
        x[k]=0
        subsetsum(cs,k 1,r-w[k],x,w,d)
#driver for the above code
w=[2,3,4,5,0]
x=[0,0,0,0,0]

subsetsum(0,0,sum(w),x,w,7)