Lesson 1

Let us recall our recursive code for the knapsack problem, which simply enumerates all subsets.

def knapsack(capacity, weights):
    def helper(idx, items):
        if idx != len(weights):
            return max(helper(idx + 1, items), helper(idx + 1, items + [weights[idx]]))
        return sum(items) if sum(items) <= capacity else 0

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


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

27

In each recursive call we pass two parameters: \(\texttt{idx}\) and \(\texttt{items}\). The first parameter is the index of the item we need to make a decision about at this step (whether to take it or not). The \(\texttt{items}\) parameter represents the set of items taken among the first few (more precisely, among the items with indices from zero to \(\texttt{idx}-1\)). But if we look closely, we see that what we need from \(\texttt{items}\) is just one thing — the sum of its elements. So instead of \(\texttt{items}\) we can just pass this sum! We will use the variable \(\texttt{total}\) for that.

def knapsack(capacity, weights):
    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]))

27