TIL: The knapsack problem is "weakly" NP-complete. There exists algorithms to solve it in time linear in the numbers specifying the instance, but exponential in the length of (number of bits require to express) those numbers. https://en.wikipedia.org/wiki/Weak_NP-completeness