[thelist] SQL to get combo that sums to amount

[Joshua Olson]

> -----Original Message-----
> From: aspscript at canada.com
> Sent: Thursday, September 09, 2004 7:46 AM
>
> What I'm trying to do is simulate a "stock market"
> where a user places an order for a certain number of
> shares.  For example, if a user places an order to to
> buy 50 then I need to go thru and search to see if
> there is any combination of sell orders that adds to 50
> to complete the order.  So I only need to find one
> combination of records that meets this criteria and
> then I could change the status of those records.

Presuming for a second that you have access to some sort of procedural
language, like perhaps stored procedures, then it seems that you may be
interested in a greedy algorithm.  As others have mentioned, to get ALL
combinations that add up to 50, then you'd need to enumerate all possible
combinations.  That number could be fairly massive depending on the number
of individual records.

Development of a greedy algorithm, with a bit of recursion, may get you to
where you need to be.  In this case, do something like the following:

- Select the highest sell order that is <= the buy order.
- Reduce the buy order by that amount
- Continue selecting the sell orders that are <= the modified buy amount

Ideally, if there are a bunch of onsies on the sell side, then you should be
able to land dead-on the amount with only a few iterations of the above
algorithm.  If you don't land straight on the amount, ignore the highest
sell amount and start again.  If you haven't found the combination by the
time that the remaining non-ignored sell orders add up to less than the buy
amount then you can be fairly certain that you aren't going to find a good
combination.

While this solution may not be 100%, it's a lot better than an exhaustive
search.  You could probably do better with a dynamic algorithm[0], but I'm
going to leave that as an exercise for you if you want to look into that.

0. http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/

<><><><><><><><><><>
Joshua Olson
Web Application Engineer
WAE Tech Inc.
http://www.waetech.com/service_areas/
706.210.0168