[petermcneeley]

The knapsack problem here is of particular interest since despite the optimization problem being NP-hard the solution can in fact be found in O(n * W). This feels similar to how the theoretical best comparison sort is O( n log n) but radix can do this in O( n).

[mesarvagya]

Knapsack still is a NP-Hard Problem. Even though DP solution looks linear, it has pseudo-polynomial time complexity[1][2]

[1]https://en.wikipedia.org/wiki/Knapsack_problem#Computational...

[2] https://stackoverflow.com/questions/4538581/why-is-the-knaps...