AlgoScope

Branch and Bound

Backtracking with a bound. Prune any branch whose best possible outcome cannot beat the current best.

Algorithmic paradigms, paradigm, advanced
Bound 7 against best 0: explore.ABCDweightvalue23453456
Bound 7 against best 0: explore.ABCDweightvalue23453456

Branch and Bound: Four items, most of the tree cut

Decision, step 2 of 7

Deciding item A with nothing taken, weight 0 of 5, value 0. Fill the remaining 5 optimistically, fractions allowed: the bound is 7. The best complete answer is 0. The bound is higher, so the branch might still win: explore it, taking A first.

Cost

Space
O(depth)