找零问题求解

今天我们来分享一个大家都喜闻乐见的问题 -- 找零问题。

为什么说会喜闻乐见呢？这不想多了嘛，都跟你谈钱了，还需要多说什么吗。

说到钱，我们就不说闲话了，直接来看下今天的分享内容吧。

本文中会用到 贪心算法 和 动态规划 ，不太明白的同学可以自行查阅这两种算法的内容，或者之后我们来做相关的分享。

首先来看如何使用贪心算法来求解。以及何时可以使用贪心算法求解。

1. 贪心算法的求解

栗子🌰：

假设当前有1、2、5、10、20、50、100 等面额的纸币，请你使用最少的纸币数量来找零。

像这种问题的找零问题就可以使用贪心算法来求解，因为所有的前置项相加的和不会超过当前元素。

如：

1 + 2 < 5

1 + 2 + 5 < 10

1 + 2 + 5 + 10 < 20

代码示例：

function minCount(amount) {
  let values = [1,2,5,10,20,50,100]
  let result = 0

  while(amount) {
    amount -= values.filter(item => item <= amount).pop()
    result++
  }
  return result
}

代码解释：

首先遍历所有可能的元素，并获得最接近当前零钱的最大值。
将当前钱数递减，每次递减将结果 +1, 直到需要的钱数为0

2.适用动态规划的情况

栗子🌰：

假设当前的纸币金额只有 1,5,11这三种，这样的情况下我们适用贪心就不能取得最优解。原因如下：

需要找零的金额为 15元，若使用上面的贪心算法，就会出现 11,1,1,1,1 这种组合。

实际上我们只需要 5,5,5三张纸币就OK了。

于是，我们开了大招变了身，放弃了贪心算法，通过动态规划解决了这个问题。

2.1 动态规划第一版

let values = [1,5,11]
function minCoins (amount) {
  let min = amount

  if (amount < 1) {
    return 0
  }
  if (values.includes(amount)) {
    return 1
  }

  // 查找 values 中小于 amount 的所有值。
  let middle = values.filter(item => item < amount)

  for (let i = 0,len = middle.length; i < len; i++) {
    // 这里的 1 相当于先找一张，然后剩下的金额继续计算。
    let newMin = 1 + minCoins(amount - middle[i])
    if (newMin < min) {
      min = newMin
    }
  }
  return min
}
minCoins(15) // 3

代码解析：

如果当前的金额小于 1 ，不需要找零，返回 0
如果当期的金额存在于纸币列表中，表明只需要一张就可以，返回1。
不在列表中，且不小于 1 的情况：
- 查找到小于金额的纸币列表
- 尝试找回一张纸币
  - （代码 1 + minCoins(amount - middle[i])中的1 这个内容。）
- 继续递归计算剩余金额，需要的最小数量。
  - （代码 1 + minCoins(amount - middle[i])中的amount - middle[i] 这个内容。）
- 如果获得的最小值小于min 则更新min值
- 将当前得到的最小值返回。

上面这种解法在执行过程中大家会发现一个问题，即使当前金额之前做过计算，接下来还有相同金额的时候还需要重新计算，这样就多了一层计算消耗。

解决的方法也很简单，只需要将每次计算的结果缓存下来即可。

2.2 动态规划第二版

let values = [1,5,11]
let cache = [] // 缓存之前的结果
function minCoins (amount) {
  let min = amount

  if (amount < 1) {
    return 0
  }
  if (values.includes(amount)) {
    return 1
  }
  if (cache[amount]) return cache[amount] // 如果有缓存，直接取得缓存中的结果

  let middle = values.filter(item => item < amount)

  for (let i = 0,len = middle.length; i < len; i++) {
    let newMin = 1 + minCoins(amount - middle[i])
    if (newMin < min) {
      min = newMin
    }
  }
  cache[amount] = min // 将当前计算的最小值缓存下来。
  return min
}

这里就是将我们计算得到的最小最做缓存。

在每次求解之前查看是否有缓存本次金额的最小纸币数量。

如果命中缓存，则直接返回缓存中的内容。

好了，以上就是我们本次分享的内容。希望本次分享的内容能为你带来帮助哟。

下次再见，Bye~