1. 简介
在本篇文章中，我们将学习如何使用贪心算法来求解一个经典问题：给定金额，求使用最少数量的硬币进行找零。这个问题也被称为找零问题（Change-Making Problem）。
我们会从问题定义开始，接着介绍贪心算法的解决思路，并通过一个实际例子来演示算法的执行过程。然后给出算法的伪代码和时间复杂度分析，最后指出该方法的局限性，并提出替代方案。
2. 找零问题定义
我们被提供一个硬币面额数组 D = {d1, d2, ..., dm}，其中每个面额可以无限使用。我们的目标是找出一个硬币组合数组 S，使得这些硬币的面额之和等于给定金额 n，且硬币数量最少。
举个实际例子：
假设我们手头有无限数量的面额为 D = {1, 2, 10} 的硬币，现在需要给顾客找零 n = 15 元，最少需要多少枚硬币？
3. 解决思路
贪心算法通过每一步选择当前可用的最大面额硬币来构造解。其核心思想是：
- 从最大面额开始尝试，尽可能多地使用该面额；
- 每次使用后，将总金额减去该面额；
- 直到金额减为 0。
示例解析
我们用上述例子来演示算法的执行过程：
- 当前金额为 15，最大面额是 10，使用 1 枚，金额变为 5；
- 最大可用面额是 2，使用 2 枚，金额变为 1；
- 使用 1 枚 1 元硬币，金额归零。
最终硬币组合为 S = {10, 2, 2, 1}，共 4 枚硬币。
4. 算法伪代码
algorithm findMinimumNumberOfCoins(D, m, n):
// D：硬币面额数组
// m：面额种类数
// n：目标金额
// S：返回的硬币组合数组
Sort D in ascending order
S = empty array
for i from m - 1 downto 0:
while n >= D[i]:
add D[i] to S
n = n - D[i]
if n == 0:
break
return S
时间复杂度分析
- 排序操作时间复杂度为
O(m log m) - 遍历和减金额的操作最多执行
n次，因此时间复杂度为O(n) - 总体时间复杂度为
O(n)，因为m通常远小于n
5. 局限性
⚠️ 贪心算法的一个重要局限性是：在某些面额组合下，它不能给出最优解
示例说明
假设面额为 D = {1, 6, 10}，要找零 n = 13：
- 贪心算法会选择
10 + 1 + 1 + 1 = 13，共 4 枚硬币 - 实际最优解是
6 + 6 + 1 = 13，只需 3 枚硬币
这是因为贪心算法每一步都只选择当前局部最优解，而不能回溯或综合考虑全局情况。
✅ 解决方案：在这种情况下，我们可以使用动态规划（Dynamic Programming）来获得全局最优解。
6. 小结
- 贪心算法是一种简单高效的找零问题求解方法；
- 在某些面额组合下，它能快速给出最优解；
- 但在其他组合下，它可能给出非最优解；
- 如果需要保证最优性，应使用动态规划方法。
贪心算法适合用于面额为标准货币单位（如人民币、美元等）的场景，比如在收银系统中实现快速找零。
如果你在实际项目中使用该算法，请务必确认面额组合是否满足贪心选择性质，否则建议使用动态规划。