Here's my little recursive solution: import Monad import List makeChange :: [Integer] -> Integer -> Integer -> [[Integer]] makeChange coins amount maxCoins | amount < 0 = [] | amount == 0 = [[]] | null coins = [] | amount `div` maximum coins > maxCoins = [] -- optimisation | amount > 0 = do x <- coins xs <- makeChange (filter (<= x) coins) (amount - x) (maxCoins - 1) guard (genericLength (x:xs) <= maxCoins) return (x:xs) makeChange' :: Integer -> Integer -> [[Integer]] makeChange' amount maxCoins = makeChange coins amount maxCoins where coins = [200,100,50,20,10,5,2,1] -- Cale On 13/07/05, Dinh Tien Tuan Anh <tuananhbirm@hotmail.com> wrote:
Hi, The problem is: Given an amount of money m, and unlimited coins of value 1p, 2p, 5p, 10p, 20p, 50p, £1 and £2 List ALL (distinct) ways of change for m, using no greater than k coins
eg: m = 75, k = 5 => [50, 20, 5] [50, 20, 1,2,2] .......... .........
i have been familiar with the "integer parition" problem, but how to generalise to solve the one above ?
Is this problem suitable for functional programming language ?
Any idea ? Cheers
_________________________________________________________________ It's fast, it's easy and it's free. Get MSN Messenger 7.0 today! http://messenger.msn.co.uk
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe