[Haskell-cafe] Coin changing algorithm
chrisk at MIT.EDU
Wed Jul 13 11:35:11 EDT 2005
Okay, I like Cale's extra guard short circuit so much I must add it to
> amount `div` maximum coins > maxCoins =  -- optimisation
> partition (x:xs) m k | x>m = partition xs m k -- x is too big
> parititon (x:_) m k | x*k < m =  -- cannot succeed
> partition (x:xs) m k | otherwise =
> let most = min k (div m x)
> range = [most,most-1..1]
> use quantity = (\quantity -> prefix (replicate quantity x)
> (partition xs (m-quantity*x) (k-quantity))
> in map use range
> The first result from this will be the greediest.
As for memoizing, it would be interesting to attack it differently.
Get all the results for a given m and unlimited k and store them sorted
by k. Then return the list via takeWhile length up to k. Next call for
same m can skip to the takeWhile and be very fast.
Pre-generating the table for amounts up to some limit could be done more
efficiently with a bottom up approach.
More information about the Haskell-Cafe