Skip to content

Instantly share code, notes, and snippets.

@samidarko
Created March 9, 2018 03:41
Show Gist options
  • Save samidarko/686f7d6dd207e3e4e976d414ac3c764e to your computer and use it in GitHub Desktop.
Save samidarko/686f7d6dd207e3e4e976d414ac3c764e to your computer and use it in GitHub Desktop.
naive greedy algorithm in Haskell
import qualified Data.Map as M
amount = 18
coins = [5, 4, 2, 1]
greedy a cs = fn a cs M.empty
where
fn _ [] m = m
fn x (y:ys) m = let t = x `div` y
in if t > 0 then fn (x-t*y) ys (M.insert y t m)
else fn x ys m
main :: IO ()
main = do
let result = greedy amount coins == M.fromList [(1,1),(2,1),(5,3)]
putStrLn ("greedy amount coins == M.fromList [(1,1),(2,1),(5,3)] is " ++ show result)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment