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

Question

在class中，我们讨论了子集和问题的解决方案（给定一组正数 S，是否存在 S 的子集总和为正值 T）。这是我的 python 算法实现和一个简单的测试用例：

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

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

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

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

Why does basic Subset Sum algorithm not handle negative values?

python

algorithm

subset-sum