Post
Topic
Board Development & Technical Discussion
Re: SelectCoins algorithm
by
2112
on 18/10/2011, 18:08:15 UTC
I am trying to understand the SelectCoins function (at least at a high level):
It computes an approximate solution to an one-dimensional knapsack problem. In textbooks it is typically posed as finding a maximum lower than the size of the knapsack (to minimize the empty space). Here it is inverted: the goal is to find minimum higher than the size of the knapsack (to minimize the change required).

Whatever you do, don't reinvent the wheel, there's a rich literature on this problem.