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

1. find all tx outputs that meet the following conditions
- sent to me (have a hash160 belonging to a key in my wallet)
- have not been spent yet
- are in a confirmed block
2. sort the outputs smallest to largest amount
3. for each output
- create an input that references it and add to current_amount
- break if current_amount > amount i want to send
4. create one output (change) sending the difference back to me at a new address

naive indeed! This will tend to generate _much_ larger transactions that required and will pretty much not work on many wallets.

Consider what happens when someone rains a bunch of 1e-8 inputs on you and then you try to send 1BTC ... your resulting TXN will be too big and will be either need enormous fees and may be ignored by your peers and the miners even with fees.

The subset sum solver isn't just an optimization. It's an important optimization.

(The actual coin selection in bitcoin could be a lot better too... right now its fee blind and will tend to produce solutions that pay fees which could be avoided the only real defense against this is that pre-filtering that makes it first try inputs with many confirms, unfortunately good solvers for big integer programming problems aren't small pieces of code)