Branch and Bound
Backtracking with a bound. Prune any branch whose best possible outcome cannot beat the current best.
Branch and Bound: Four items, most of the tree cut
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)