I first encountered the Knapsack problem at a job interview. Intuitively I tried to solve it using what I later found out to be the greedy approximation algorit

I first encountered the Knapsack problem at a job interview. Intuitively I tried to solve it using what I later found out to be the greedy approximation algorithm [1], which proved unsuccessful to solve it for the interview's sample input. Since I had not much time left I switched to an inefficient brute force approach, basically a test of all possible combinations, which wasn't well received by the interviewer back then since he was expecting a recursive dynamic solution [2]. When I started a blog last year I decided to revisit this problem while writing about complexity classes of problems, and tried to demonstrate how to translate a solver to the Knapsack problem for solving another NP-complete problem, the partition problem [3] ;) It's indeed a very interesting and fun problem to tackle! [1] https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approx... [2] https://github.com/TCGV/Knapsack/blob/master/Tcgv.CombinatorialOptimization/KnapsackProblem/RecursiveDynamicSolver.cs https://github.com/TCGV/Knapsack/blob/master/Tcgv.Combinator... [3] https://thomasvilhena.com/2019/08/complexity-classes-of-problems https://thomasvilhena.com/2019/08/complexity-classes-of-prob...