1

私はHaskellにかなり慣れていないので、「金額（セント単位）が与えられた場合、金種のリストが与えられたときに変更を行うすべての方法を決定する」という問題に対する解決策を改善する方法に興味があります。

change :: Int -> [Int] -> [[Int]]
change amt [] = [[]]
change amt [d] = [replicate (quot amt d) d]
change amt (d:denoms) =
 if d <= amt then
   reverse [0..(quot amt d)] >>= \x ->
     [(replicate x d) ++ c | c <- (change (amt - (x*d)) denoms)]
  else
    change amt denoms

changeUS amt = change amt [25, 10, 5, 1]

-- *Main> changeUS 29
-- [[25,1,1,1,1],[10,10,5,1,1,1,1],[10,10,1,1,1,1,1,1,1,1,1],[10,5,5,5,1,1,1,1],[10,5,5,1,1,1,1,1,1,1,1,1],[10,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,5,1,1,1,1],[5,5,5,5,1,1,1,1,1,1,1,1,1],[5,5,5,1,1,1,1,1,1,1,1,1,11,1,1,1],[5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]

このソリューションの問題点の 1 つは、最小のデノムが 1 であると想定していることchange amt [d]です。その場合、 が均等に割り切れるif/thenことを確認するために an を追加できますが、少し冗長になり始めており、より良い解決策ではそのケースは必要でさえないと思います。amtd

4

1 に答える 1

5

これを行う最も簡単な方法は、ブルートフォースです。

-- assumes the denominations are distinct. If they aren't, the
-- return value is ambiguous
change :: [Integer] -> Integer -> [[Integer]]
change _  0 = [[]]
change [] _ = []
change xxs@(x:xs) n | n >= x    = map (x:) (change xxs (n - x)) ++ change xs n
                    | otherwise = change xs n

貪欲なアプローチが機能しない場合には完全に免疫があり、入力リストがソートされているかどうかは気にしません。宗派が明確でない場合に失敗する唯一の理由は、出力形式が異なるリストを区別しないことです。その場合の入力。同じ金額の異なる入力を区別するために出力タイプを変更した場合、同じアルゴリズムが機能します。

分岐が多い場合は遅くなる可能性がありますが、変更の問題ではそうではありません。また、生産的に怠惰であるため、消費者が部分的な出力で意味のあることを行うことができれば、段階的に出力を生成できます。

于 2013-06-21T19:29:05.203 に答える