Lesson 5

Enumeration with such optimizations is called the branch and bound method. The name speaks for itself: we grow the branches of the recursion tree and try to bound the objective function in each branch to decide whether it is worth continuing it. This method is heuristic: we didn’t prove any upper bound on its runtime, but it works fast on various datasets in practice. For example, it instantly processes the input that was too hard for our first solution: \(\texttt{capacity=300, weights=[2] * 100}\).