子集和问题
|
最近,我对子集和问题感兴趣,该问题正在超集中找到零和子集。我在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
没有找到相关结果
已邀请:
6 个回复
雄鞋谋塘
您可以找到启发式方法,这仅使您有机会在多项式时间内找到精确解。 另一方面,如果使用集合中数字值的界限将问题(仅限于另一个问题),则问题的复杂度将降低为多项式时间。但是即使那样,消耗的内存空间仍将是非常高阶的多项式。 消耗的内存将远远大于您的内存中的几GB。 甚至比硬盘驱动器上的几个TB还要大。 (那是为集合中元素的值的界的小值) 动态编程算法可能就是这种情况。 在我看来,构建初始化矩阵时使用的是1000的范围。 您可以尝试较小的范围。也就是说...如果您的输入始终由小值组成。 祝好运!
寇剩
我花了几分钟时间,效果很好。
糖固傻染
,而是将函数的实际代码放入循环中,以避免函数调用的开销。 希望有帮助!干杯
断跑胺弄萎
一些建议: 尝试使用一维列表并使用bitarray来最小化减少内存占用(http://pypi.python.org/pypi/bitarray),因此您只需更改get / set functon。这样至少可以减少64位的内存占用(列表中的整数是指向整数丝毫类型的指针,因此可以是3 * 32的因子) 避免使用try-catch,但是在开始时找出适当的范围,您可能会发现自己将获得巨大的速度。
貉骂
输入输出如下:
唤副埂侧壬