貪婪演算法(Greedy)，是在每一步選擇中都選擇最佳的選項而希望導致結果為最好的演算法，這種演算法再解決有最佳子結構的問題時能得到良好的效率，與動態規劃不同的是貪婪演算法在每個子問題都進行解決方案的選擇，因為不具儲存運算結果的功能，因此無法進行回推的操作。

範例說明 :

題目 : 找零問題

假設你有一堆不同面額的硬幣，並且你需要找零給顧客。你的目標是用最少的硬幣數量來達成這個找零目標。給定一個面額清單和一個找零的目標金額，請計算所需的最少硬幣數量。

1. 輸入 硬幣面額 {1, 5, 10, 25}
2. 找零目標 : 30

過程 :

Step1 : 將硬幣金額由大排到小，優先使用金額較大的硬幣

Step2 : 對排序過後的硬幣進行遍歷，對於不同面額減去相應的金額，直到達成找零目標

Step3 : 回傳所需硬幣數量的最小值

程式碼 :

int minCoins(const std::vector<int>& coins, int amount) {
    int count = 0;
    //將硬幣由大到小進行排序
    std::vector<int> sortedCoins = coins;
    std::sort(sortedCoins.rbegin(), sortedCoins.rend());

    for (int coin : sortedCoins) {
        while (amount >= coin) {
		        //減去硬幣面額
            amount -= coin;
            //增加硬幣數量
            count++;        
        }
        if (amount == 0) {
		        //完成找零
            break; 
        }
    }
		//回傳所需的最少硬幣數量
    return count;
}

int main() {
    std::vector<int> coins = {1, 5, 10, 25};
    int amount = 30;
    int result = minCoins(coins, amount);
    std::cout << "最少硬幣數量: " << result << std::endl;
    return 0;
}

優點 :

1. 計算效率高，時間複雜度通常較低，適合大規模的數據
2. 較容易擴展到其他相似的問題

缺點 :

1. 貪婪演算法不能保證找到最佳的答案
2. 貪婪演算法依賴問題的結構，並不適用於所有結構的問題