如何实现js贪心算法解决钱币找零问题的代码示例？

本文共计657个文字，预计阅读时间需要3分钟。

给出一组硬币的面值，以及需要找零的钱数，计算出找到零钱的最小硬币数量。

例如，美国硬币面值有1分、5分、10分、25分这四种，若要找零36美分，则最少需要1个25分、1个10分和1个1分硬币。

给定一组硬币的面额，以及要找零的钱数，计算出符合找零钱数的最少硬币数量。

例如，美国硬币面额有1、5、10、25这四种面额，如果要找36美分的零钱，则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。

对于每一种面额，我们都分别计算所需要的硬币数量。具体算法如下：

1. 如果全部用1美分的硬币，一共需要36个硬币
2. 如果用5美分的硬币，则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
3. 如果用10美分的硬币，则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
4. 如果用25美分的硬币，则需要1个25美分的硬币 + 1个10美分的硬币 + 1个1美分的硬币 = 3个硬币

示意图

方案4的硬币总数最少，因此为最优方案。