演算法›Ch7 貪婪演算法第 2 題/共 12 題
2. 貪心演算法、找零錢問題
#AL-07-002易貪心演算法找零錢問題
Consider the problem of making change for cents using the fewest number of coins. An algorithm to solve this problem is to give the coin with the highest available denomination without going over, and repeat the process until the amount of remaining change drops to 0. Which of the following sets of available coin denominations would cause this algorithm to fail at yielding an optimal solution?
參考答案與解析
答案 (B) :這是找零錢貪心演算法失敗的經典反例。要湊出7元,貪心會先取5、再取1、再取1,共3枚硬幣;但最佳解是4+3,只需2枚硬幣,貪心並非最佳。(A)(C)(D)(含(C)的標準美元幣值、(D)任何等比幣值 )都可以證明貪心法在這些幣值系統下一定能得到最佳解。
📄 台大110
▤完整推導請見《WH 資工筆記 · 演算法》Ch7 貪婪演算法