Knapsack Problem

Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the approximation ratio, is the difference between a heuristic that might be terrible and an algorithm with a written contract about how far from optimal its answer can be. **Approximation Algorithms** introduces that contract-based view of NP-hard optimization. You will define approximation ratio formally and walk through the classic constant-factor algorithms: a 2-approximation for Vertex Cover via greedy maximal matching, an `O(log n)`-approximation for Set Cover via greedy element-counting, and a 2-approximation for Metric TSP that exploits the triangle inequality on top of an MST. The lesson then covers approximation schemes (PTAS, polynomial in `n` for any fixed `epsilon`; FPTAS, polynomial in both), with Knapsack FPTAS as the canonical example. Throughout, the lesson contrasts approximation algorithms with heuristics, where heuristics give no guarantee at all. In **Greedy (Intro)**, you saw simple greedy strategies and their correctness proofs. **Dynamic Programming (Advanced)** introduced 0/1 Knapsack as an NP-hard exact algorithm. This lesson asks the next question: when exact is too slow, how close to optimal can we provably get? Next, **Advanced Bit Manipulation** turns to bit-level tricks for `O(1)` and bitmask-DP solutions.

0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound. **Branch and Bound** introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach. In **Backtracking (Intro)**, you walked an implicit decision tree with choose, explore, unchoose. **Greedy (Intro)** taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other. Next, **Divide and Conquer (Advanced)** turns to algebraic D&C tricks like Karatsuba and Strassen.

Edit distance, the minimum number of insertions, deletions, and substitutions to turn one string into another, is what every spell checker quietly computes when it suggests a correction. The DP table that solves it has `m * n` cells, each filled by looking at three neighbors. That single 2D recurrence is the gateway to a much larger family: longest common subsequence, knapsack, palindrome partitioning, regex matching, and many more. **Dynamic Programming (Advanced)** is where 1D DP graduates into the rest of the field. You will work through 2D grid and string DP (unique paths, edit distance, LCS, longest common substring), the knapsack family (0/1, unbounded, subset sum, coin change), sequence DP (LIS in `O(n^2)` and the patience-sorting `O(n log n)` variant, maximum product subarray, word break), string DP (palindromic subsequence and substring, regex and wildcard matching), DP on trees (diameter, max path sum, binary tree cameras), interval DP via matrix chain multiplication, and an introduction to bitmask DP for TSP and assignment problems. In **Dynamic Programming (Intro)**, you learned to define state, transition, and base cases on linear problems. This lesson layers a second dimension onto each. Next, **Advanced DP Techniques** introduces optimization tools that push DP beyond standard tabulation.