舟拿着100元去买糖吃,买了糖后要找零时,发现店里只剩下1元、2元和5元的纸币了。找回来一大堆零钱确实很烦人,所以小舟要求店员找给他的纸币的数量必须是最少的。 已知需要找还的钱的数额,同时店里有充足的1、2、5元纸币供找兑。编写一个程序,计算以最少数量的纸币凑出找零的数额时,各种纸币的使用数量。
时间: 2024-03-23 18:36:43 浏览: 136
用贪心算法实现购物找零(支付+找零使用最少硬币数)
5星 · 资源好评率100%
好的,这是一道典型的动态规划问题。我们可以定义一个数组dp[i]表示凑出i元钱所需要的最少纸币数。对于每个i,我们可以考虑使用1元、2元或5元纸币,那么:
- 如果我们使用1元纸币,那么需要的纸币数就是dp[i-1]+1;
- 如果我们使用2元纸币,那么需要的纸币数就是dp[i-2]+1;
- 如果我们使用5元纸币,那么需要的纸币数就是dp[i-5]+1。
最后,dp[i]就是上述三个数中的最小值。可以通过循环遍历0到目标数额,依次求解dp数组,最终得到各种纸币的使用数量。
下面是Python代码实现:
```python
def findMinCoins(target):
coins = [1, 2, 5] # 纸币面值
dp = [0] * (target+1) # 初始化dp数组
for i in range(1, target+1): # 从1到target逐个求解
dp[i] = float('inf')
for coin in coins:
if i >= coin and dp[i-coin]+1 < dp[i]:
dp[i] = dp[i-coin] + 1
# 回溯求解各种纸币的使用数量
count1, count2, count5 = 0, 0, 0
while target > 0:
if target >= 5 and dp[target-5] == dp[target]-1:
target -= 5
count5 += 1
elif target >= 2 and dp[target-2] == dp[target]-1:
target -= 2
count2 += 1
else:
target -= 1
count1 += 1
return count1, count2, count5
```
你可以直接调用findMinCoins函数,传入目标数额,即可得到各种纸币的使用数量。
阅读全文