Can someone provide an implementation for O(NsqrtN) Knapsack?

Revision en2, by Anthony_Smith, 2022-03-18 04:38:27

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Anthony_Smith 2022-03-18 04:40:35 21 Tiny change: 'orces.com/topic/59937/en9), which u' -> 'orces.com/blog/entry/59606), which u'
en2 English Anthony_Smith 2022-03-18 04:38:27 2
en1 English Anthony_Smith 2022-03-18 04:37:56 1251 Initial revision (published)