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。否则，change amt [d]情况将不正确。我可以添加一个if/then以确保在这种情况下amt可以被整除d，但它开始变得有点冗长，我认为这种情况在更好的解决方案中甚至不是必需的。

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