Dynamic program vs integer program: which one is better for knapsack problem?
The field of optimization encompasses many different fields of models and algorithms. You can classify the field base on many different critierias: Linear vs nonlinear, convex vs non-convex, continuous vs discrete, etc. Often times, one problem could be solved with multiple different approaches, and this is where different underlying solution philosohpies meet each other, which I find very interesting. In this article, we are going to dive deeper into the difference between dynamic programming and integer programming with the interesting and well-studied problem of knapsack problem.