Okay, I like Cale's extra guard short circuit so much I must add it to my pseudo-example.
Cale's guard: > amount `div` maximum coins > maxCoins = [] -- optimisation Mine, updated. > > 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. -- Chris _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
