Python中的子集和(动态编程)-复杂性问题

Question

我在Python中解决子集和问题的函数的某些实现中遇到了问题。

我们这里有动态规划，所以复杂度应该是多项式。

问题是，如果集合的大小线性增长，并且数字的大小也线性增长(当然不是数字的对数)，那么代码执行时间可以指数增长。

我的猜测是，这可能是由于某个特定的实现。有可能以某种方式改进它吗？

Python代码：

def subsetsum(array,num):
if num == 0 or num < 1:
return None
elif len(array) == 0:
return None
else:
if array[0] == num:
return [array[0]]
else:
with_v = subsetsum(array[1:],(num - array[0])) 
if with_v:
return [array[0]] + with_v
else:
return subsetsum(array[1:],num)

Answer 1

您使用切片来传递array的后缀，这将生成一个具有线性运行时间的副本。为了避免这种情况，您可以传递索引。另一个优点是索引是可散列的，因此您可以缓存(或记忆)并避免重新计算答案：

from functools import lru_cache
def ssum(array, N):
@lru_cache(maxsize=None)
def subsetsum(idx, num):
if num < 1 or idx >= len(array):
return frozenset()
if array[idx] == num:
return frozenset([idx])
with_v = subsetsum(idx + 1, num - array[idx])
if with_v:
return with_v | frozenset([idx])
else:
return subsetsum(idx + 1, num)
return list(array[i] for i in subsetsum(0, N))

>>> ssum([1,1,2], 4)
[1, 1, 2]

不幸的是，仍然需要复制从后缀中获得的答案