确定分裂变化的方式

Question

我对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]]

该解决方案的一个问题是它假设最低的denom将为1.否则,该change amt [d]情况将是不正确的.我可以添加一个if/then以确保在这种情况下amt可以被整除d,但它开始变得有点冗长,我认为在更好的解决方案中甚至不需要这种情况.

Answer 1

到目前为止,最简单的方法就是蛮力.

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

它完全不受贪婪方法不起作用的情况的影响,它不关心输入列表是否被排序,并且当面额不明显时它失败的唯一原因是输出格式不区分不同的在这种情况下输入.如果您更改输出类型以区分具有相同面额的不同输入,则相同的算法将起作用.

在有很多分支机构的情况下,这种情况可能会很慢,但这不太可能发生在变革问题上.如果消费者可以通过部分输出做任何有意义的事情,那么它也是高效懒惰的,因此能够逐步产生输出.