7

最近我开始对子集和问题感兴趣，该问题是在超集中找到一个零和子集。我在 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
4

6 回答 6

5

我不太确定您的解决方案是准确的还是 PTA（多时间近似）。

但是，正如有人指出的那样，这个问题确实是 NP-Complete 的。

意思是，每个已知（精确）算法在输入大小上都有指数时间行为。

这意味着，如果您可以在 0.01 纳秒内处理 1 个操作，那么对于 59 个元素的列表，它将需要：

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

您可以找到启发式方法，这使您有机会在多项式时间内找到精确的解决方案。

另一方面，如果您使用集合中数字的值的界限来限制问题（到另一个），那么问题的复杂性会降低到多项式时间。但即便如此，消耗的内存空间也将是一个非常高阶的多项式。
消耗的内存将比内存中的几 GB 大得多。甚至比硬盘驱动器上的几 TB 大得多。

（这是针对集合中元素值的小界限值）

可能这就是您的动态编程算法的情况。

在我看来，您在构建初始化矩阵时使用了 1000 的界限。

您可以尝试较小的范围。那就是……如果您的输入始终由小值组成。

祝你好运！

于 2011-05-17T00:33:21.520 回答
5

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 []

我用了几分钟，效果很好。

于 2011-06-10T15:24:01.483 回答
1

此处提供了一篇关于优化 python 代码的有趣文章。基本上，主要结果是您应该内联您的频繁循环，因此在您的情况下，这意味着不是get_element每个循环调用两次，而是将该函数的实际代码放在循环内以避免函数调用开销。

希望有帮助！干杯

于 2011-05-16T07:44:26.080 回答
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. 尝试使用一维列表并使用 bitarray 以至少减少内存占用（http://pypi.python.org/pypi/bitarray），因此您只需更改 get / set 功能。这应该将您的内存占用至少减少 64 （列表中的整数是指向整数 whit 类型的指针，因此它可以是因子 3*32）

  2. 避免使用try-catch，但在开始时确定适当的范围，您可能会发现您将获得巨大的速度。

于 2011-05-16T20:24:16.383 回答
0

以下代码适用于 Python 3.3+，我在 Python 中使用了 itertools 模块，它有一些很好的方法可以使用。

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')

于 2017-02-06T03:07:02.923 回答
0

只需更改集合 w 中的值，并相应地使数组 x 与 w 的 len 一样大，然后将 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)
于 2017-05-27T12:12:41.183 回答