Solving the Knapsack problem is pretty easy, it's probably the textbook example for explaining branch-and-bound algorithms. What you probably had in mind is that it's NP-complete, meaning that we don't know any polynomial-time algorithms and most experts think that none can be found, although nobody has been able to prove that (this is the famous P=NP? problem).
Which is why the OP says:
> Find counterexamples to each of the following algorithms for the knapsack problem.
Anyway, yes, in the strictest sense of the term, it is unsolved because it's NP-complete, however it's been thoroughly analyzed in many different ways (it's pseudo-P, we have a MITM algo, different flavors of approximations, etc.)
NP-complete doesn't mean unsolvable! It means that we don't know any algorithms that run in subexponential time for every input. But of course we can use the algorithms with exponential worst case running time. We can also use algorithms that solve most instances fairly quickly but may take a very long time to solve some particularly hard instances.
Yes, I don't disagree with any of this. Let me rephrase that. The problem of determining what is the minimum asymptotic time complexity for an algorithm that correctly solves any knapsack instance is unsolved.
Actually, the knapsack problem allows taking an item more than once. The problem described in the blog is the 0-1 knapsack problem which can be solved in polynomial time.
Hello HN - author here. Yes, I did audit this entire course over the fall of 2018 (edited again in 2019).
In fact, very soon I will have a podcast episode out with Prof. Skiena to talk about his book and the course.
Any questions or comments you want to shoot over please reach out!