Generation of Combinatorial Objects · Branch and Bound Method

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Let us recall our code for enumerating all subsets and adapt it to the knapsack problem. 

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

Let us also recall how exactly this code enumerates all subsets: