makeChange :: Int -> [Int] -> [Int]
makeChange amt [] = []
makeChange amt (c:cs) = (amt `div` c) : makeChange (amt `mod` c) cs
{-
This is my first thought to implement the makeChange function.
However, it is not good, for example:
makeChange 18 [10, 9, 3, 1] = [1, 0, 2, 2]
which is not good, the right solution is [0, 2, 0, 0].
This problem seems more difficult.
In fact, it may related to discrete mathematic’s numerical partitions problem.
After some research, this seems like classic problem as:
money-changing problem
coin-changing problem
Numerical Partitions problem
… etc
Here are some references:
http://theory.cs.uvic.ca/amof/e_partI.htm
http://www.mathematik.uni-bielefeld.de/~sillke/PUZZLES/denumerants
http://en.wikipedia.org/wiki/Schur’s_theorem
So, … maybe come back later to fix it.
-}
This entry was posted
on Tuesday, May 22nd, 2007 at 4:29 pm and is filed under Haskell - SOE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
November 14th, 2007 at 5:03 pm
This is what I came up with:
makeChange :: Int -> [Int] -> [Int]
makeChange amt cs = pretty $ foldl1 (\x y -> if (sum x)
November 14th, 2007 at 5:05 pm
Sorry, that got cut off. Do need to use the html entity for less than?
makeChange :: Int -> [Int] -> [Int]
makeChange amt cs = pretty $ foldl1 (\x y -> if (sum x) < sum y then x else y) ccs
where makeChange’ _ [] = []
makeChange’ amt (c:cs) = (amt `div` c) : makeChange’ (amt `mod` c) cs
ccs = map (makeChange’ amt) (subs cs)
pretty xs = (replicate ((length cs) - (length xs)) 0) ++ xs