tags: APCS

d904_v2－換零錢

題目連結： d904

題目解析

這題的問題是經典的「找零問題」（Coin Change Problem），要求你使用最少數量的硬幣來湊出特定的金額。題目給定N種不同面額的硬幣，以及需要湊出的總金額C，目標是找出所需的最少硬幣數量。

解題方向

這類問題通常可以用動態規劃（Dynamic Programming）來解決。動態規劃的基本思想是將問題分解為一系列子問題，並利用這些子問題的解來構建原問題的解。

1. 問題轉化：
   • 我們要找出如何用最少數量的硬幣來湊出C美分。
   • 定義一個數組method[i]，其值代表湊出i美分所需的最少硬幣數量。
2. 狀態轉移：
   • 對於每一種硬幣面額coin[k]，如果我們已經知道湊出j - coin[k]美分的最少硬幣數量，那麼我們可以嘗試使用這枚硬幣來湊出j美分。
   • method[j]可以透過比較當前的值和method[j - coin[k]] + 1來得到最小值。
3. 初始條件：
   • 當金額為0時，所需的硬幣數量是0，即method[0] = 0。
   • 對於其他金額，初始時設為一個很大的數字（如100000），表示還沒有找到有效的硬幣組合。
4. 結果輸出：
   • 當所有計算完成後，method[C]就是湊出C美分所需的最少硬幣數。

程式解析

1. 初始化：
   • method[]陣列的大小是C+1，所有值初始化為100000（表示初始無法湊出）。
   • method[0]設為0，因為湊出0美分不需要任何硬幣。
2. 動態規劃迴圈：
   • 第一個迴圈遍歷所有的硬幣種類，第二個迴圈計算從當前硬幣面額到總金額C的最少硬幣數量。
   • 在每次迴圈內，根據已知的結果（湊出j - coin[i]的最少硬幣數量），計算湊出金額j所需的最少硬幣數。
3. 結果輸出：
   • 最後的結果存儲在method[C]中，表示湊出C美分所需的最少硬幣數量。

完整程式碼

# 讀取輸入
s = input()
C, N = map(int, s.split())

coin = []
method = [100000 for _ in range(C+1)]  # 初始化method數組，設為一個大數

for i in range(N):
    coin.append(int(input()))  # 讀取所有硬幣面額

method[0] = 0  # 初始化method[0] 為 0，因為湊出 0 美分不需要硬幣

# 動態規劃的核心部分
for i in range(N):  # 遍歷每種硬幣
    for j in range(coin[i], C+1):  # 遍歷從當前硬幣面額到C的所有金額
        if method[j] > method[j - coin[i]] + 1:  # 如果使用當前硬幣可以使硬幣數量更少
            method[j] = method[j - coin[i]] + 1  # 更新最少硬幣數量

print(method[C])  # 輸出湊出C美分所需的最少硬幣數量

補充說明

C = 6 （目標金額為6美分）
N = 3 （有3種不同的硬幣）
硬幣面值 = [1, 3, 4]

1. 初始化：

   • 將method[0]設為0，因為組成0美分需要0個硬幣。
   • 將method[1]至method[6]初始化為100000，作為一個很大的數值，表示尚未找到更好的解。

2. 開始處理每種硬幣：

   • 對於第一種硬幣（1美分）：
     • j 從1循環到6。
     • 每次循環時，將method[j]與method[j - coin[i]] + 1進行比較。由於coin[i]此時為1，這意味著每個method[j]將與method[j - 1] + 1比較。
     • 例如，當j = 1時，method[1]（初始為100000）將與method[0] + 1（即1）進行比較，顯然1更小，因此method[1]更新為1。這一過程將持續下去，導致method[1]至method[6]分別更新為1, 2, 3, 4, 5, 6。
   • 對於第二種硬幣（3美分）：
     • j 從3循環到6。
     • 當j = 3時，method[3]（此時為3，使用了三個1美分硬幣）將與method[3-3] + 1（即method[0]+1=1，表示使用一個3美分硬幣）進行比較。因為1<3，所以method[3]更新為1。
     • 當j = 4時，method[4]（此時為4，使用了四個1美分硬幣）將與method[4-3] + 1（即method[1]+1=2，表示使用一個3美分硬幣加上一個1美分硬幣）進行比較。因為2<4，所以method[4]更新為2。
     • 當j = 5和j = 6時，類似地更新method[5]為3（使用一個3美分和二個1美分硬幣）和method[6]為2（使用兩個3美分硬幣）。
   • 對於第三種硬幣（4美分）：
     • j 從4循環到6。
     • 當j = 4時，method[4]已經是2，使用一個3美分和一個1美分硬幣。method[4-4]+1（即method[0]+1=1，表示使用一個4美分硬幣）更小，所以method[4]更新為1。
     • 當j = 5時，改為用2個硬幣（原本是3個）。
     • 對於 j = 6，更新過程繼續，但由於method[6]已經是最小（2個硬幣），所以它不會再有更新。

3. 輸出結果：程式最後輸出method[C]的值，即組成C美分（在此例中為6美分）所需的最少硬幣數。在此例中，method[6]的值可能是2，表示最少需要兩個硬幣來達成目標金額。這兩個硬幣的組合可能是兩個3美分的硬幣，或者一個4美分加上兩個1美分的硬幣。

4. 額外補充：

   當我們看到 method[j - coin[i]] + 1：

   • j - coin[i] 表示從當前目標金額 j 中扣除一個 coin[i] 面值的硬幣後，剩下需要組成的金額。
   • method[j - coin[i]] 就是組成這個剩餘金額所需的最少硬幣數，這個值是之前計算過並保存在 method[] 陣列中的。
   • +1 表示加上我們剛扣除的那一個 coin[i] 硬幣。

   所以，method[j - coin[i]] + 1 這個表達式的含義是：如果我們從目標金額 j 中使用掉一個 coin[i] 硬幣，那麼加上這一個硬幣，總共需要的最少硬幣數是多少。