tags: APCS

d904－換零錢

題目連結： d904

題目解析

這道題目要求我們在給定的硬幣面額和總金額的情況下，找到用最少數量的硬幣來湊齊總金額的方案。由於硬幣面額的數量是有限的，因此問題的重點在於如何合理地選擇硬幣面額，以最小化所需硬幣的數量。

舉例來說，假設我們有 5 種不同面額的硬幣（1, 5, 10, 25, 50），需要湊齊 93 美分。最理想的情況是選擇最大面額的硬幣來湊大部分金額，然後用剩下的硬幣面額來湊餘額。這樣可以減少總共需要的硬幣數量。

解題方向

1. 貪心算法的應用：這道題目可以使用貪心算法來解決。貪心算法的核心在於每一步選擇當下最優的解，即每次選擇面額最大的硬幣來湊總金額，這樣能保證使用的硬幣數量最少。
2. 硬幣排序：將所有硬幣面額按照從小到大的順序排列，以方便在後續的計算中逐個檢查面額。
3. 逐步遞減：從最大的面額開始，依次選擇面額較大的硬幣來減少需要湊齊的總金額。當使用某個面額的硬幣無法完全湊齊金額時，再繼續使用面額次大的硬幣，直到湊齊總金額為止。

程式解析

1. 輸入讀取與初始化：
   • 首先讀取總金額 C 和硬幣種類數目 N，以及 N 種不同面額的硬幣，並將這些面額存入 coin 列表中。
   • 將 coin 列表中的硬幣面額按從小到大的順序排序，這樣可以在後續操作中方便從最大的硬幣面額開始進行計算。
2. 貪心算法的應用：
   • min_nums 初始設定為全部使用最小面額硬幣來湊齊總金額時的硬幣數量，這是一個初始的最糟情況。
   • 使用兩層循環遍歷所有硬幣面額的組合：
   • 外層循環逐步減少考慮的硬幣面額種類數，從最大面額開始依次減少。
   • 內層循環則嘗試使用當前面額的硬幣來湊齊金額，並逐步減少面額直到湊齊總金額。
3. 結果輸出：
   • 將計算出的最少硬幣數量 min_nums 作為結果輸出，這就是在最佳情況下湊齊總金額所需的最少硬幣數。

完整程式碼

#
# Greedy = NA 90%, 有一個不是最佳解
#
#start
row = input()
row = row.split()
C = int(row[0]) # 總金額
N = int(row[1]) # 硬幣種類數目

# row = input()
# C, N = map(int, row.split())
#


coin = []
for i in range(N):
    value = int(input())
    coin.append(value)

coin.sort() # 硬幣由小到大排序

min_nums = int(C/coin[0]) # 使用最小面額硬幣找零時所需的最大硬幣數量
# 例：總金額：100元，最小是1元的話，1元的最大數量為100 

for i in range(N):
    num = 0
    now_C = C

    for j in range(N-1-i, -1, -1):
        num += int(now_C/coin[j])
        now_C %= coin[j]

    print(i, num)

    if num<min_nums:
        min_nums = num
# 透過兩層循環遍歷所有硬幣組合：
	# 外層循環逐一減少考慮的硬幣種類數。
	# 內層循環從最大的硬幣面額開始，盡可能多地使用當前面額的硬幣，然後逐步降低硬幣面額，直到找零完成。
print(min_nums)