Lesson 3

If the input set of numbers is small, this code works fast. But as the size of the set grows, this program quickly becomes impractical. For example, the call \(\texttt{knapsack(300, [2] * 100)}\) will never finish. Indeed, modern computers perform about \(10^{9}\) basic operations per second. The \(\texttt{knapsack}\) method enumerates all \(2^{n}\) subsets of a given \(n\)-element set. Let's see how many years this program would need to go through \(2^{100}\) options: \[\frac{2^{100}}{365 \times 24 \times 60 \times 60 \times 10^9}\approx 40196936841331\]

Let’s think about which branches in this tree we definitely don’t need. We will consider three basic optimizations. First, if the sum of already taken numbers exceeds the capacity, we immediately terminate the current recursive call (i.e., we won’t even try to continue this branch). For example, we won’t try to extend the branch \((17, 9, 7)\): the sum in it already exceeds 28.

def knapsack(capacity, weights):
    def helper(idx, items):
        total_weight = sum(items)
        if total_weight > capacity:
            return 0

        if idx == len(weights):
            return total_weight

        return max(helper(idx + 1, items), helper(idx + 1, items + [weights[idx]]))

    return helper(idx=0, items=[])


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

27

Second, we will maintain the maximum value already found and use it as follows: if in the current branch we cannot exceed this maximum even by taking all remaining numbers, we will not consider this branch further. In other words, if it is already clear that the current branch cannot find a better solution than the one already known, there is no point wasting time on it. Third, to make the previous optimization more effective, we will swap the two recursive calls: we’ll first go to the branch where we take the current number, and then to the branch where we don’t take it. As a result, the code will look like this:

def knapsack(capacity, weights):
    optimum = 0

    def helper(idx, items):
        nonlocal optimum

        total = sum(items)
        if total > capacity or total + sum(weights[idx:]) <= optimum:
            return
        elif idx == len(weights):
            optimum = max(optimum, total)
        else:
            helper(idx + 1, items + [weights[idx]])
            helper(idx + 1, items)

    helper(idx=0, items=[])
    return optimum


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

27
200