Hi 我是 eop 。 畢業於台灣大學資訊工程系（NTU CSIE）， 現在是 Sifive 的 Compiler Engineer。 （Ex-Skymizer Compiler Engineer） 你可以在 eopxd.com 找到我！ 我會發布一些對技術的整理、閱讀或觀影的心得或是生活的感悟。 如果覺得這些創作有價值，歡迎支持我。 希望人生能一直過得有趣又有挑戰。
Canonical Coin System
什麼時候一個錢幣系統可以透過 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
Original link: eopXD
喜欢我的文章吗？
别忘了给点支持与赞赏，让我知道创作的路上有你陪伴。
发布评论…