Lesson 2

This code will still run forever on our old test dataset \[\texttt{capacity=300, weights=[2] * 100}.\] But the reason for this bad behavior will be different now. Previously all recursive calls differed in parameters: all of them had different pairs \(\texttt{(idx, total)}\). But now it may happen that many recursive calls will have exactly the same parameters. And this is exactly what happens in practice! To verify this, insert a debug print line at the start of the \(\texttt{helper}\) method: \(\texttt{print(idx, total)}\) and run it on the dataset \(\texttt{capacity=300, weights=[2] * 100}\). You will see an endless stream of output:

def knapsack(capacity, weights):

    def helper(idx, total):
        print(idx, total)
        if idx == len(weights):
            if total <= capacity:
                return total
            else:
                return 0
        else:
            return max(
                helper(idx + 1, total),
                helper(idx + 1, total + weights[idx])
            )

    return helper(0, 0)


print(knapsack(28, [17, 9, 7, 3]))

99 16
100 16
100 18
98 16
99 16
100 16
100 18

The standard way to avoid this is memoization. Its idea is simple and natural: if we already computed something, let’s save the result somewhere so we don’t have to recompute it next time. This is a purely technical point, and there is an out-of-the-box solution for it: the cache decorator saves the results of recursive calls that have already been made.

from functools import cache


def knapsack(capacity, weights):
    @cache
    def helper(idx, total):
        if idx == len(weights):
            return total if total <= capacity else 0
        else:
            return max(helper(idx + 1, total), helper(idx + 1, total + weights[idx]))

    return helper(idx=0, total=0)


print(knapsack(capacity=28, weights=[17, 9, 7, 3]))
print(knapsack(capacity=300, weights=[2] * 100))

27
200