コインを減らす払い方

いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。

支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。

例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。

change :: Int -> [Int]

change 0 = []

change n | n >= 5000 = 5000 : (change $ n - 5000)

         | n >= 1000 = 1000 : (change $ n - 1000)

         | n >= 500 = 500 : (change $ n - 500)

         | n >= 100 = 100 : (change $ n - 100)

         | n >= 50 = 50 : (change $ n - 50)

         | n >= 10 = 10 : (change $ n - 10)

         | n >= 5 = 5 : (change $ n - 5)

         | otherwise = 1 : (change $ n - 1)
pay2_ :: Int -> [Int] -> Maybe [Int]

pay2_ 0 l = Just l

pay2_ n [] = Nothing 

pay2_ n (c:cs) = 

    case c of 

      c | n < c -> Just $ change (c - n) ++ cs

      c | otherwise -> pay2_ (n - c) cs
pay2 :: Int -> [Int] -> Maybe [Int]

pay2 n l = 

    let sorted = sort l in

    pay2_ n sorted

解説：
change はおつりを返す関数．
できるだけ少ない数でお釣りを返してくれる．

pay2_ は計算の本体．
sort された手持ちのお金リストが入力されることを期待している．
戦略としては小さい順に使っていって、オーバーしたらオーバー分のお釣りをコインのリストで返す．
実際，例えば [1, 10] (1円1枚、10円一枚) 持っているときに 5 円払おうとすると，普通は10 円だけ払おうとすると思うけど，この戦略では 11 円で払おうとする．
でもまあ、それでもうまく返ってくるので良しとする．
とはいえ、この戦略で本当に最小枚数かどうかは分からないので投稿はしませんw

実行結果



Main > pay2 5 [1,10] 

Just [5,1]

追記：
やはりというか、渡したお金が返ってくるような渡し方は禁止されたようです．
従ってこの記事の解は不正解となりました．