高考申論題
110年
[資訊處理] 資料結構
第 一 題
📖 題組：
假設收銀機內銅板的集合 S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額 W=$75。(一)請設計一個 Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。（15 分）(二)此 Greedy 演算法適合使用何種資料結構來完成。（5 分）(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）
假設收銀機內銅板的集合 S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額 W=$75。(一)請設計一個 Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。（15 分）(二)此 Greedy 演算法適合使用何種資料結構來完成。（5 分）(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）
📝 此題為申論題，共 3 小題
小題 (一)
請設計一個 Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。（15 分）
思路引導 VIP
- 演算法設計：貪婪演算法在找零問題中的核心策略是「每次都選擇當前剩餘找零金額下，面額最大且不超過該剩餘金額的硬幣」。2. 步驟拆解：列出目前剩餘金額 -> 掃描可用硬幣 -> 選擇最大硬幣 -> 更新剩餘金額。3. 注意：本題給出的銅板集合 $S$ 是有限的（不是無限量供應），所以選走一個要扣除一個。
小題 (二)
此 Greedy 演算法適合使用何種資料結構來完成。（5 分）
思路引導 VIP
思考貪婪演算法的核心操作：每次都要取「最大值」。什麼資料結構能高效地提供最大值？1. 排序後的陣列（Sorted Array）：取第一個元素。2. 最大堆積（Max-Heap）：根節點即為最大值，取出後調整時間複雜度為 $O(\log n)$。
小題 (三)
此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）
思路引導 VIP
這是貪婪演算法的經典反例考題。貪婪法在「貨幣系統為規整面額（如 1, 5, 10, 50）」時有效，但在任意面額下通常只能得到可行解而非最佳解。找一個反例即可：目標金額小於貪婪選取的總和，而存在另一組更少數量的組合。
貪婪演算法找零問題
💡 每步選擇當前最大面額以期達到全局最優，但結果未必最佳。
🔗 貪婪找零演算法執行鏈
- 1 降冪排序 — 將收銀機內所有面額依大到小排列
- 2 局部最優選取 — 選取目前最大且小於等於剩餘金額的硬幣
- 3 狀態更新 — 目標金額減去硬幣面額，並將該硬幣從集合移除
- 4 結束條件 — 直到金額歸零或無硬幣可用為止
↓
↓
↓
🔄 延伸學習：延伸學習：當 Greedy 失效時，需改採動態規劃 (DP) 求解。
