|
|
|
|
|
|
by pietjepuk88
2861 days ago
|
|
|
Aside from the special case of "1" always being present, I would say that in general you should just use an optimizer to solve knapsack problems. Whether you should do so for an interview question is up for debate I guess; using libraries shows you can get something done quickly and efficiently, but implementing your own solver might show you understand the underlying complexity. As far as comparing code complexity of Julia to Python is concerned, I would say that when you use JuMP in Julia, you should use Pyomo/CasADi/PuLP/... in Python. That is not to say that I don't find JuMP to be a more appealing framework overall. It has wide support for all kinds of solvers, and some Julia/JuMP authors even wrote fairly good MIQCP/MICP solvers on top of commercial/open-source MILP/SOCP solvers. |
|
|
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
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.