python - 为什么基本子集和算法不处理负值？

Question

在类里面，我们讨论了子集求和问题的解决方案(给定一组正数 S，是否存在总和为正值 T 的 S 子集)。这是我用一个简单的测试用例实现的算法:

def ss(s, i, t):
    if t == 0:
        return True
    if i == (len(s)-1):
        return s[i] == t
    return ss(s, i+1, t-s[i]) or ss(s, i+1, t)

s = [1, 3, 5]
t = 8 
print(ss(s, 0, t))
>> True

我们应该为可以处理 S 和 T 中的负值的修改后的算法制定并证明其正确性。但是，到目前为止，我在未修改的算法上尝试过的每个具有负值的集合似乎仍然有效。我似乎找不到此算法因负值而失败的示例。

有人可以向我解释为什么该算法不适用于所有负值，并可能给出一个反例来证明这一点吗？

Answer 1

这确实适用于负数。也许，如前所述，这个想法是用不同的前置条件和后置条件来证明算法的正确性？取决于你如何证明它的正确性。

请注意，这在 Python 中有效，因为该语言中没有明确的“自然数”限制。如果您使用的是伪代码或更具限制性的编程语言，这些限制会更有意义。希望对您有所帮助。