branch and bound
Backtracking is great when you only need any solution that satisfies the rules. But many problems ask for the best solution — the cheapest route, the most valuable knapsack, the shortest schedule. Branch and bound is backtracking upgraded for optimization: as you explore, you keep the best complete solution found so far, and you compute, at each partial solution, an optimistic estimate of the best any of its completions could achieve. If even that optimistic estimate cannot beat the best you already have, you prune the whole subtree — there is no point looking inside.
The two halves are in the name. Branch is the same as backtracking: split a partial solution into the choices of the next decision, building the state-space tree. Bound is the new idea: at each node you compute a bound on the objective over all completions of that node — a lower bound for a minimization problem (the best, i.e. smallest, cost any completion could have) or an upper bound for a maximization. You also track the incumbent, the value of the best complete solution seen so far. The pruning rule: if a node's optimistic bound is no better than the incumbent (for minimization, if the node's lower bound is >= the incumbent), then no completion of that node can improve on what you have, so discard the node. A good bound is usually a relaxation — solve an easier version that ignores some constraints (for example, allow fractional items in knapsack) to get a quick optimistic value.
Correctness rests entirely on the bound being valid: it must never be more optimistic than the truth (a minimization lower bound must really be <= every completion's cost), or you could prune away the actual optimum. Given a valid bound, branch and bound returns a provably optimal answer while often visiting far fewer nodes than full enumeration. The catch is that the worst case is still exponential — a weak bound prunes little — and the method's speed lives or dies on how tight the bound is and how good the order of exploration is (exploring promising nodes first raises the incumbent quickly, which makes later pruning more aggressive).
For 0/1 knapsack (maximize value within a weight cap), at a partial choice compute an upper bound by greedily filling the remaining capacity with the best value-per-weight items, allowing a fractional last item (the fractional-knapsack relaxation). If that optimistic bound is <= the value of the best full packing found so far, drop this branch — no honest completion can do better.
Branch like backtracking, but prune a subtree whenever its optimistic bound can't beat the best solution found so far.
The bound must be optimistic-but-valid: a minimization lower bound that is ever too high (above some completion's true cost) can prune the optimum and silently return a wrong answer — a looser, always-valid bound is safer than a tight, occasionally-invalid one.