Branch and Bound

Systematically explores a decision tree like backtracking, but at every node computes an optimistic bound (here, the fractional-knapsack relaxation) — if the bound can't beat the best solution found so far, the entire subtree is pruned without being visited.

Category: Algorithmic Techniques
Time complexity: O(2ⁿ) worst, much less in practice
Space complexity: O(n)

Pseudocode

at each node: compute optimistic upper bound
if bound ≤ best found so far: prune (skip subtree)
else: recurse into both include/exclude branches

Reference implementation

def branch(i, w, v):
    best[0] = max(best[0], v)
    if i == n or bound(i, w, v) &lt;= best[0]:
        return  # prune
    if w + wt[i] &lt;= CAP: branch(i+1, w+wt[i], v+val[i])
    branch(i+1, w, v)

Open the interactive Branch and Bound visualisation →