用python,结账时,营业员要给顾客找零。营业员手里有10元、5元、1元(假设1元为最小单位)几种面额的钞票,其希望以尽可能少(张数)的钞票将钱换给顾客。比如,需要找给顾客17元,那么其需要给顾客1张10元,1张5元,2张1元。而不是给顾客17张1元或者3张5元与2张1元。(输入样例中“5”表示可以换算金额的次数)
时间: 2024-02-03 22:13:32 浏览: 113
以下是一个用贪心算法求解的 Python 代码实现:
```python
def change_money(total, bills):
"""
:param total: 需要找零的总金额
:param bills: 面额列表,按降序排列,如[10, 5, 1]
:return: 返回一个字典,键为面额,值为需要的张数
"""
result = {}
for bill in bills:
num = total // bill
if num > 0:
result[bill] = num
total -= num * bill
if total == 0:
break
return result
# 示例使用
total = 17
bills = [10, 5, 1]
print(change_money(total, bills))
```
输出:
```
{10: 1, 5: 1, 1: 2}
```
这个函数的核心思想就是每次选择最大的面额进行找零,直到找完为止。这个方法可以保证找到的张数最少,但并不能保证一定是最优解(即最小张数)。
阅读全文