1

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

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

4

2 回答 2

1

让我们想要制造，并且每个硬币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，一种解决方案——我们没有钱，正是一种解决问题的方法——选择不找硬币，或者更准确地说，选择硬币找零

  2. count(n,m) =0, n<0, 无解——负金额

  3. count(n,m) =1, n>=1, m<=0，没有解决办法——我们有钱，但没有找零

于 2015-11-08T06:06:30.063 回答
1

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

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

注意：

  1. 给定的解决方案假设硬币列表是 desc 排序的
  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]]

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

解释

  1. 第一个条件 d==0 && n==0 定义了找到的单一解决方案：我们有零数量要找零，零硬币要包括在找零中；
  2. 接下来的三个条件定义了无法找到解决方案；
  3. d>=coin 这意味着给定的金额高于一组硬币中的第一枚硬币，所以在这里我们必须选择：使用第一枚硬币进行解决方案搜索或不使用该组的第一枚硬币进行搜索
  4. 对于第一枚硬币高于金额的情况，我们只能在不使用第一枚硬币的情况下进行
于 2015-11-08T06:08:09.377 回答