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
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