概念

貪心，又稱為貪婪演算法，簡單來說它的運作模式就是每一步選擇都選擇當下最好的選項，或是選擇不會比其他選擇還要糟的選項，所以其實大多數時候在實作 greedy 都是非常直觀的想法與方式，不過不一定可以輕易證明正確性

實作

因為有點難單純透過程式碼講解，因此在這邊透過題目解說

UVa 11369 - Shopaholic

題目大意

有一個人要買下商店內所有商品，現在有買二送一，想問他最多可以省下多少錢

解題思路

基本上買二送一是送最低價格的商品，因此很直觀的思考，如果要將省下的錢最大化就是要盡量讓送的商品高價，因此可以直接想，將商品價格排序之後從最貴的商品開始三個三個一組買下，這樣就可以使省下的錢最大化了

AC Code

#include<bits/stdc++.h>
using namespace std;
int p[20100];
int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 0;i < n;i++){
            cin >> p[i];
        }
        sort(p,p + n);
        long long ans = 0;
        for(int i = n - 3;i >= 0;i -= 3){
            ans += p[i];
        }
        cout << ans << "\n";
    }
    return 0;
}

證明

其實 greedy 最難的點不在於實作，而是在於如何證明他是正確答案，像是這一題的證明就可以以下方的重點思考

• 當數量不到 3 個時，無法買二送一，只能原
• 當數量剛好 3 個時，只能免費掉最便宜的第 3 個，沒有別的選擇
• 當數量大於 3 個時，也可以分成上面的兩種狀況思考

綜合以上可以整理成

• 數量 n 3 無法打折，最佳解為全部單買
• 數量 n 3 且 n 為 3 的倍數，最便宜的打折，剩下的最佳解就會是剩下 n − 1 件商品的最佳解
• 數量 n 3 且 n 不為 3 的倍數，最便宜的 n % 3 直接單買不會影響到最佳解，所以此時的最佳解和前 n − n % 3 貴的商品一樣

不過這是因為這一題比較好證明一點，有些題目其實不像這題這麼直觀，所以也要多多練習題目與證明才會更加熟練，而最快可以證明出貪心準則不正確的方式就是直接舉出反例來證明

成立的要件

基本上如果要 greedy 可以成立有一個最重點的地方，就是之前的選擇一定不會影響後面的選擇，這樣才可以不斷的選擇局部最佳解，然後全部執行結束後才會得到整體的最佳解

總結

本文介紹 greedy 的基本概念運作模式，並強調如何才能使用 greedy，除此之外，也提供一題題目範例語證明。最後，指出確定是否可以使用 greedy 解決問題的要件。希望這篇文章能夠幫助大家更深入理解 greedy。