Branch and Bound — 0/1 Knapsack Search Tree

At each node we compute the fractional (optimistic) bound. If bound ≤ incumbent (best-so-far), the whole subtree is pruned (crossed out). Watch the incumbent tighten and pruning kick in.

step 0

Search tree (take = solid green, skip = dashed)

current node new incumbent pruned (bound ≤ best) infeasible (overflow)

State

capacity W = 10
incumbent (best) = 0
node bound = —
nodes visited = 0
subtrees pruned = 0
items sorted by value/weight ratio
Press Step to begin. We branch take / skip on each item, computing a fractional upper bound and pruning any subtree that cannot beat the incumbent.
Self-contained visualization. The fractional bound = value taken + greedily-packed whole remaining items + a fraction of the next item that overflows; it is an admissible upper bound, so a subtree with bound ≤ best can never improve the answer and is safely pruned. See junior.md and professional.md for the optimality proof.