> I would say that in general you should just use an optimizer to solve knapsack problems. Why do you say that? Perhaps if the knapsack problem is provably non

> I would say that in general you should just use an optimizer to solve knapsack problems. Why do you say that? Perhaps if the knapsack problem is provably non-polynomial, but being able to distinguish those cases is a rather important skill. For example, the problem you specified can more easily be solved directly: https://repl.it/repls/RotatingObeseBusinesses https://repl.it/repls/RotatingObeseBusinesses With respect to the interview question context, if I had a candidate that implemented a solver, I would be inclined to say they completely overengineered the solution for a less optimal answer. There are a bunch of assumptions that are required for a solver to be optimal and unless the candidate can enumerate all of them and argue why the problem meets those constraints, the solver is not 100% guaranteed to be correct, whereas a direct solution is. Not to mention, as you noted, edge cases, and the complete cryptic-ness of the code.