Quote from: 2112 on October 18, 2011, 06:08:15 PM

Quote from: bitcoinandroid on October 18, 2011, 06:23:08 AM

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.

Well, ideally (but not in the official bitcoin today) it's complicated by an additional integer-linear constraint: You want the priority to be greater than the fee minimum unless there isn't a feasible solution with that constraint.

You also want to avoid creating change less than 0.01 btc, all things equal, unless you have a real output smaller than 0.01 btc or if meeting this constraint causes you to fail the prior one. (in which case, abandoning this one is better)