Задача о сумме подмножеств

Недавно я заинтересовался проблемой подмножества-суммы, которая заключается в нахождении подмножества с нулевой суммой в надмножестве. Я нашел несколько решений на 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
652   6  

6 ответов:

Я не совсем уверен, является ли ваше решение точным или PTA (Poly-time approximation).

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

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

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

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

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

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

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

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

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

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

Удачи!

5  
2011-05-17 03:33:21

Кто-то в 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 []
Я провел с ним несколько минут, и он работал очень хорошо.
4  
2011-06-10 18:24:01

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

Надеюсь, это поможет! Ура

1  
2011-05-16 16:49:25

, 1-й глазок 

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

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

1  
2011-05-17 00:01:22

Следующий код работает для 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')
0  
2017-02-06 05:07:02

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

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)
0  
2017-05-27 19:54:58

Comments

    Ничего не найдено.
Click here to cancel reply.