动态规划（使用确切数量的硬币进行精确更改）

Question

我有无限的 4 种硬币：[1, 5, 25, 50]。如何挑选 EXACT 48 个硬币来准确找零 1 美元？（以任何一种有效方式）

我知道如何递归解决这个问题，但是否可以使用 DP 解决它？如何？谢谢！

Answer 1

假设我们想要制造 n cents，并且每个 S = { S1, S2, S3, .. Sm } 个硬币都可以无限供应。

动态编程方法：

为了计算解决方案的总数，我们可以将所有解决方案分成两组

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

设count(S[], m, n)为计算解数的函数，则可写为sum of count(S[], m-1, n) and count(S[], m, n-Sm) .

因此公式为

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

具有以下基本情况：

count(n,m) =1, n=0，一个解决方案——我们没有钱，完全是解决问题的一种方法——选择不找零，或者更准确地说，选择零找零
count(n,m) =0, n<0,无解--负数钱
count(n,m) =1, n>=1, m<=0，无解——我们有钱，但没有零钱

Answer 2

可能的解决方案可能如下（Haskell）：

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

注意：

给出的解决方案假设硬币列表是 desc 排序的
不处理给定值无法更改的情况 - 我只是没有包括检查，只是演示这个想法
要更改的输入值以美分为单位

以下是一些结果：

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

因此，它给出了用 48 个硬币找零 100 美分的所有可能解决方案

说明

第一个条件 d==0 && n==0 定义找到的单一解决方案：我们有零金额要找零，零硬币要包含在零钱中；
接下来三个条件定义找不到解；
d>=coin 这意味着给定的数量高于一组硬币中的第一个硬币，所以在这里我们必须选择：继续解决方案搜索 用第一个硬币 或继续没有第一个硬币组
对于第一个硬币高于金额的情况，我们只能不使用第一个硬币

动态规划（使用确切数量的硬币进行精确更改）

Dynamic Programming (to make exact change using exact number of coins)

algorithm

recursion

dynamic-programming

coin-change