動態編程（使用確切數量的硬幣進行確切的更改）

Question

我有無限4種類型的硬幣：[1，5，25，50]。 如何挑選EXACT 48金幣做出準確的1元零錢嗎？（在任何一個有效的辦法）

我知道如何遞歸地解決這個問題，但有可能它採用DP解決？怎麼樣？謝謝！

Answer 1

的可能的解決方案如下（哈斯克爾）：

change d coins | null coins = [] 
       | d==0 = [] 
       | d>=coin = coin:change (d-coin) coins   
       | otherwise = change d (tail coins) where 
     coin = head coins 

需要注意的是：

1. 給定的解決方案假定硬幣列表已經過排序
2. 情況下不能改變給定值沒有被處理 - 我只是不包括支票，只是驗證這個想法
3. 輸入值的變化是仙

下面是一些結果：

*Main> change 100 [50, 25, 5, 1] 
[50,50] 
*Main> change 99 [50, 25, 5, 1] 
[50,25,5,5,5,5,1,1,1,1] 
*Main> change 75 [50, 25, 5, 1] 
[50,25] 

如果在解決方案中使用硬幣的數量限制：

exactChange d coins n 
    | d==0 && n==0 = [[]] 
    | d>0 && n==0 = [] 
    | d==0 && n>0 = [] 
    | null coins = [] 
    | d>=coin = useFirstCoinSolutions ++ skipFirstCoinSolutions 
    | otherwise = skipFirstCoinSolutions where 
    coin = head coins 
    rest = tail coins 
    useFirstCoinSolutions = map (\x->coin:x) $ exactChange (d-coin) coins (n-1) 
    skipFirstCoinSolutions = exactChange d rest n 

這給出了以下結果：

*Main> exactChange 100 [50, 25, 5, 1] 48 
[[25,25,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],[25,5,5,5,5,5,5,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],[5,5,5,5,5,5,5,5,5,5,5,5,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]] 

因此，它給出了變化的所有可能的解決方案100％的具有精確48枚硬幣

說明

1. 第一條件d == 0 & & n ==可0定義了單個溶液中發現：我們沒有改變的金額和剩餘的零幣以包含在變化中;
2. 接下來的三個條件定義了找不到解;
3. d> =硬幣，這意味着給量比一套硬幣所以這裏的第一個硬幣高，我們必須選擇：繼續解決方案搜索與第一硬幣或繼續沒有該組第一硬幣
4. 對於情況下，當第一個硬幣比量較高，我們只能繼續不使用第一硬幣

Answer 2

讓我們想要使n cents，我們給每個S = { S1, S2, S3, .. Sm }硬幣無限供應。

動態規劃方法：

要計算解決方案的總人數我們可以把所有的一整套解決方案爲兩套

1. 不包含mth coin (or Sm)解決方案。
2. 包含at least one Sm的解決方案。

讓count(S[], m, n)是計算解決方案的號碼的功能，那麼就可以寫成總和count(S[], m-1, n)和count(S[], m, n-Sm)。

因此配製成

count(n,m) = count(n, m-1) + count(n- sm, m) 

通過以下基本情況：

1. count(n,m) =1, n=0，一個解決方案 - 我們沒有錢，只有一個解決問題的辦法 - 通過選擇沒有硬幣改變，或者更確切地說，選擇硬幣更換0

2. count(n,m) =0, n<0，沒有解決方案 - 負金額

3. count(n,m) =1, n>=1, m<=0，無解 - 我們有錢，但沒有可用的變化