这是解决子集和的更好方法吗？

Question

我正在尝试一种基本方法来更快地解决子集求和问题，然后我想到了这个

天真的方法是 oldSS 函数，它测试所有 2^n 组合。但后来我注意到，在检查每个案例之前，计算当前场景可能的最小值和最大值，如果目标位于该范围内，并且它可能是那里的解决方案，那么才执行场景。这是 newSS 函数。我正在测试时间，它给了我这个

9.91289400371
0.00154754789233

我可以通过将 getMinMax 值缓存到全局变量中来进一步缩短 newSS 时间。然而对于朴素的方法，时间可以提高到 2^(n/2) 使用一个聪明的 hack，将初始列表减少 2，然后对每个列表进行朴素的方法，然后比较两个生成的列表。

但是相比2^(n/2)运行的时间，有谁知道newSS函数的效果如何？

谢谢

import timeit
from random import randint

def oldSS(lst, acc, target):
    if lst:
        return oldSS(lst[1:], acc+lst[0], target) or oldSS(lst[1:], acc, target)
    return acc==target

def randomList():
    l = []
    for i in range(20):
        l.append(randint(0,1000))
    return l
def getMinMax(lst):
    mi = 0
    mx = 0
    for i in lst:
        if i < 0:
            mi += i
        elif i > 0:
            mx += i
    return (mi, mx)
def newSS(lst, acc, target):
    if lst:
        a = False
        b = False
        mimx = getMinMax(lst[1:])

        nmi = acc+lst[0] + mimx[0]
        nmx = acc+lst[0] + mimx[1]
        if target >= nmi and target <= nmx:
            a = newSS(lst[1:], acc+lst[0], target)

        nmi = acc + mimx[0]
        nmx = acc + mimx[1]
        if target >= nmi and target <= nmx:  
            b = newSS(lst[1:], acc, target)
        return a or b
    return acc==target


if __name__ == '__main__':
    print timeit.timeit('oldSS(randomList(), 0, 60)', number=10, setup="from __main__ import oldSS,randomList")
    print timeit.timeit('newSS(randomList(), 0, 60)', number=10, setup="from __main__ import newSS,getMinMax,randomList")

Answer 1

您的新方法称为分支定界，并在算法和复杂性理论的研究中进行了非常详细的分析。

众所周知，分支定界法可以降低问题的最佳案例复杂度。然而，最坏的情况永远不会改变。考虑一组数字，其中小计的下限和上限非常接近目标。在那种情况下，您不能删减搜索中任何有意义的部分 space。平均而言，您可以显着缩短运行时间。计算分支定界算法的确切平均情况复杂度有点困难，因为分支定界方法对输入分布非常敏感。我有根据但有点生疏的猜测是你的新算法的复杂性不会低于 O(2^n/2)。

如果您需要关于渐近计算复杂性的科学答案，我建议您做一些研究，或者您可以在 CS stack exchange 上提问。如果您只是想了解哪种方法效果更好，您可以设置实证试验来比较它们。这样的试验将是最实用的方法。

这是解决子集和的更好方法吗？

Is this a better way to solve the subset sum?

python

performance

complexity-theory

np

subset-sum