在类里面,我们讨论了子集求和问题的解决方案(给定一组正数 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 中的负值的修改后的算法制定并证明其正确性。但是,到目前为止,我在未修改的算法上尝试过的每个具有负值的集合似乎仍然有效。我似乎找不到此算法因负值而失败的示例。
有人可以向我解释为什么该算法不适用于所有负值,并可能给出一个反例来证明这一点吗?
最佳答案
这确实适用于负数。也许,如前所述,这个想法是用不同的前置条件和后置条件来证明算法的正确性?取决于你如何证明它的正确性。
请注意,这在 Python 中有效,因为该语言中没有明确的“自然数”限制。如果您使用的是伪代码或更具限制性的编程语言,这些限制会更有意义。希望对您有所帮助。
关于python - 为什么基本子集和算法不处理负值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54728079/