Solving the knapsack problem with recursive queries and PostgreSQL
summary
Shows how to solve knapsack inside PostgreSQL using WITH RECURSIVE CTE that builds arrays of picked items, tracks total weight and value, and enforces constraints (bag limit 20). Example items yield an optimal set socks+hat+shoes weight 18 value 33; naive recursion first returns 25 then 33 combinations and deduping by forcing next item_id > last reduces permutations to 15. PostgreSQL 14 adds SEARCH and CYCLE to control breadth/depth traversal and detect repeats but beware cross join explosion and prune the search space.
AI-written summary · about
chapters (9)
- 0:00Introduction and travel problem
- 9:28Why solve it in PostgreSQL
- 13:17Recursive queries basics
- 18:42Adding constraints to solution
- 22:17Optimizing with item ordering
- 25:51PostgreSQL 14 search feature
- 29:41PostgreSQL 14 cycle feature
- 33:56Summary and references
- 37:08Q&A on search space pruning
related talks
46mSQL for Nerds
33mPostgres, the Best Tool You're Already Using
47mLearning advanced SQL the weird (and hard) way
42mPostgreSQL Tips & Tricks For App Devs
25mUnderstanding & Managing Postgres Table Bloat
45mSELECT 'amazing_features' FROM "postgresql"
40mAdaptive query optimization in PostgreSQL
46mUse PostgreSQL, not Rails, to make Rails Faster!