什麼時候一個錢幣系統可以透過 Greedy 得到 Optimal 呢？這個問題從中午買低 GI 便當開始⋯⋯
今天買低 GI 便當時，wanjhen 問我為什麼是帶這個硬幣數量，我說是隨手抓的，他就炫耀說他錢包裡的零錢永遠是維持 Optimal。這時我就說是 Greedy 可以解出來的，但他說是 DP 才可以。我腦袋記得關於找零錢問題的正解是 DP 沒錯可是當下腦內歸納法怎麼樣也無法在台灣錢幣系統中找到 Greedy 反例。回去跟 Yanger 講才想起原來是在特定組合下 DP 才有反例。
上網一查發現原來有人研究過這個問題了。一個 Greedy Optimal 的硬幣系統稱為 Canonical Coin System。而如果 Non-canonical coin system 的話，反例
存在於：
因此給定硬幣們，
與 
為最大硬幣面額與硬幣種類。對區間 
即可證明不存在反例。複雜度為 
。
Online Judge: PCS – Canonical Coin System
My Solution: Gist – coin.cpp
詳細證明可以看 paper ：
A polynomial-time algorithm for the change-making problem
eopXD 