Algorithm筆記 10.1 - greedy演算法練習: 找零問題

如果你也在修Coursera Algorithm Toolbox的話，這是解答！請斟酌使用

問題定義

給一個金額n，怎麼找出最少的零錢幣數目？限定幣值為{1, 5, 10}。

按照greedy algorithm步驟，我們要先找一個safe move，並且證明其為某個optimal solution的第一步。依照題目，我們假設“盡量先找幣值大的零錢是一個safe move”。

證明safe move

假設某個optimal solution = w的硬幣中有x個一元硬幣，y個5元硬幣，z個10元硬幣，如果x >= 5，我們可以拿出5個一元硬幣換成1個5元硬幣，所以optimal solution會變成w - 5 + 1 = w - 4，同理把2個y硬幣換成1個z硬幣的話，w值也會變少，得證。

演算法

private static int getChange(int m) {
    //write your code here
    int[] denominations = {10, 5, 1};
    int count = 0;

    for (int i = 0; i < denominations.length; i++) {
        int coins = m / denominations[i];
        count += coins;
        m = m - coins*denominations[i];

        if (m == 0)
            return count;
    }

    return count;
}

這是O(n)，因為我們人工去排序了幣值了。