Canonical Coin System

什麼時候一個錢幣系統可以透過 Greedy 得到 Optimal 呢?這個問題從中午買低 GI 便當開始⋯⋯

今天買低 GI 便當時,wanjhen 問我為什麼是帶這個硬幣數量,我說是隨手抓的,他就炫耀說他錢包裡的零錢永遠是維持 Optimal。這時我就說是 Greedy 可以解出來的,但他說是 DP 才可以。我腦袋記得關於找零錢問題的正解是 DP 沒錯可是當下腦內歸納法怎麼樣也無法在台灣錢幣系統中找到 Greedy 反例。回去跟 Yanger 講才想起原來是在特定組合下 DP 才有反例。

上網一查發現原來有人研究過這個問題了。一個 Greedy Optimal 的硬幣系統稱為 Canonical Coin System。而如果 Non-canonical coin system 的話,反例 w 存在於:c_{i-1} \leq w < c_{i-1}+c_j, \forall i, j

因此給定硬幣們,c_{max}|C| 為最大硬幣面額與硬幣種類。對區間 [0, 2c_{max}) 即可證明不存在反例。複雜度為 O(|C| \cdot 2c_{max})

Online Judge: PCS – Canonical Coin System
My Solution: Gist – coin.cpp

詳細證明可以看 paper :
A polynomial-time algorithm for the change-making problem

如果你覺得有收穫,可以用 30 NTD 來支持我繼續創作更多內容。因為做自己喜歡的事而得到報酬,是再好不過的事了。(街口支付)

Author: eopXD

Hi 我是 eop ,希望人生過得有趣有挑戰XD

Leave a Reply