確定拆分變更的方式

我對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整除，但它開始變得有點冗長，我認爲這種情況甚至不是更好的解決方案所必需的。

來源

2013-06-21 devth

以某種效率爲代價，您可以刪除單個面額的特例，並且有兩個基本情況：'change 0 _ = [[]]'和'change _ [] = []'。如果你想要它有效率，你需要保留最後一個面額的特例，但是如果它大於1，你可能還會花費很多昂貴的死枝。避免這種情況將需要一些數學來確定您可以從剩下的面額中完全產生什麼樣的總和。對於少量，這將比死衚衕更昂貴。 –

到目前爲止，最簡單的方法來做到這一點只是蠻力。

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

這是完全免疫的情況下貪婪方法是行不通的，它並不關心，如果輸入列表進行排序或沒有，唯一的原因時，面額不顯着失敗是輸出格式在這種情況下不區分不同的輸入。如果您更改輸出類型以區分具有相同面額的不同輸入，則可以使用相同的算法。

它在分支很多的情況下可能會很慢，但這在改變問題上不太可能。如果消費者可以對部分輸出做任何有意義的事情，它也可以增量生產輸出。

來源

2013-06-21 19:29:05 Carl

不錯！很高興看到這種風格;感覺非常習慣。 – devth

確定拆分變更的方式

回答

相關問題