(from GPT)
Milestone results (with quick why-they-matter)
・Dynamic programming origin story — Bellman’s DP framework that underlies the classic pseudo-polynomial knapsack DP. (Google Books)
・NP-completeness — Karp includes (0-1) Knapsack among his original 21 NP-complete problems (1972). This set the hardness backdrop for everything after. (cgi.di.uoa.gr)
・First FPTAS for 0-1 Knapsack — Ibarra & Kim (1975) kicked off the approximation era; later refinements followed. (SpringerLink)
・Algorithm-engineering bible (exact & approximate) — Martello & Toth’s monograph (1990). Still the go-to for classic branch-and-bound, DP variants, and benchmarks. (doc.lagout.org)
・Modern comprehensive reference — Kellerer, Pferschy & Pisinger (2004/2013) surveys the whole zoo of knapsack variants and techniques. (SpringerLink)
・Core-based exact methods — Pisinger (1997) “minimal/expanding core” made exact 0-1 knapsack solvers blisteringly fast in practice. (INFORMS Pubs Online)
Subset sum (the “pure math” spine) and lattice breakthroughs
・Meet-in-the-middle refined — Schroeppel & Shamir (1981): time (O(2^{n/2})) with only (O(2^{n/4})) space; a landmark time–space trade-off. (SIAM Ebooks)
・LLL meets subset sum — Lagarias & Odlyzko (1985): polynomial-time success on “low-density” instances via lattice reduction; later sharpened by Coster et al. (1992). This is where number theory and geometry of numbers bite. (ResearchGate)
・Near-linear pseudo-poly time — Bringmann (2016/2017): randomized (\tilde O(n+t)) for Subset Sum (target (t)), essentially tight under standard conjectures. Koiliaris–Xu (2017→2019) gave the fastest deterministic pseudo-poly. (arXiv)
・Recent worst-case advance — Nederlof–et al. (STOC’21): improves the classic Schroeppel–Shamir bound with a slick randomized algorithm. (ACM Digital Library)
Cryptographic detour (revealing the structure)
・Merkle–Hellman (1978) & Shamir’s break (1984) — Early public-key based on subset sum; Shamir’s polynomial-time attack (and later refinements) illuminated why low-density structure is fragile. (Wikipedia)
People to know (anchor researchers)
・Complexity & foundations — Richard Karp (NP-complete classification). (cgi.di.uoa.gr)
・Approximation pioneers — Oscar H. Ibarra, Chul E. Kim (FPTAS); Eugene Lawler (early approximation ideas). (SpringerLink)
・Exact algorithms / engineering — Silvano Martello, Paolo Toth; David Pisinger; Ulrich Pferschy; Hans Kellerer. (doc.lagout.org)
・Subset sum & lattices — Richard Schroeppel, Adi Shamir, Jeffrey C. Lagarias, Andrew M. Odlyzko, Marc Coster. (SIAM Ebooks)
・Modern pseudo-poly speedups — Karl Bringmann; Konstantinos Koiliaris & Chao Xu. (arXiv)
Handy “starter” reading list (one-line reasons)
・Karp (1972) — Why knapsack is hard in the worst case. (cgi.di.uoa.gr)
・Ibarra–Kim (1975) — First fully polynomial scheme; archetype of knapsack FPTAS. (SpringerLink)
・Martello–Toth (1990) — Classic cookbook of exact/approx methods that still holds up. (doc.lagout.org)
・Kellerer–Pferschy–Pisinger (2004/2013) — Encyclopedic modern treatment and variants. (SpringerLink)
・Schroeppel–Shamir (1981) — Time–space landmark for subset sum. (SIAM Ebooks)
・Lagarias–Odlyzko (1985) & Coster et al. (1992) — Lattices + low density = structural wins. (ResearchGate)
・Bringmann (2016/2017); Koiliaris–Xu (2017→2019) — Fastest pseudo-poly algorithms we have. (arXiv)