I recently came across Problem 95E. The problem pretty much asks "Given a set of coins whose values sum to $$$N$$$, find for each number from $$$1$$$ to $$$N$$$ the minimum number of coins needed to create that total sum".

I know of a way to do this with a $$$O(logN)$$$ factor (if a weight $$$w$$$ occurs $$$o$$$ times, split it up into $$$log(o)$$$ weights $$${ w, 2^1*w, 2^2*w, ..., 2^{log_2(o)} w}$$$ then do regular knapsack), but I also want to learn how to do it with a $$$O(sqrtN)$$$ factor. The general idea I've learned is that there are at most $$$O(sqrtN)$$$ distinct coin values, and that there exists some way to process all coins of one fixed coin-value in $$$O(N)$$$. But I don't know how to process all occurrences of a fixed coin-value in $$$O(N)$$$. I have read this blog, which uses the approach of finding for each total sum the minimum number of the current coin needed to create it. But the blog is for 0/1 Knapsack only, while here I want to find the minimum number of coins needed for each total sum.

Can someone provide a detailed explanation/implementation of the $$$O(NsqrtN)$$$ Knapsack Algorithm? Thanks!