Почему базовый алгоритм Subset Sum не обрабатывает отрицательные значения?

Question

В классе мы рассмотрели решение проблемы суммы подмножеств (при заданном наборе 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

Это действительно работает для отрицательных чисел.Возможно, как уже упоминалось, идея состоит в том, чтобы доказать правильность алгоритма с различными предусловиями и постусловиями?в зависимости от того, как вы доказываете его правильность.

Обратите внимание, что это работает в Python, потому что в языке нет явного ограничения "натуральных чисел".Если вы используете псевдокод или более ограничительные языки программирования, эти ограничения будут иметь больше смысла.Надеюсь, это поможет.