章節2-3.貪心演算法

什麼是貪心演算法（Greedy algorithm）？

貪心演算法的概念為，對於需要多個步驟得到的答案，在每一步驟都選擇當前最優的選擇，而非優先考慮全局最優解。用白話講就是遇到岔路時優先選看起來最好走的路，而不考慮後續可能遇到的阻礙。
很顯然的，透過「不考慮後續可能遇到的阻礙」的這個敘述，我們可以知道利用貪心得到的解可能並非最佳解。
實際情況是，在少數情況下，貪心可以得到最佳解，這種情況通常可以通過證明來保證解的最佳；而更多的情況下，貪心可以得到趨近最佳解的答案；但在特別設計過的情境下，貪心可能導致極差的解。

這裡以一個常見的例子「換錢問題」來說明這些情況。
換錢問題的基本形式是，給定n種不同面值的硬幣，每種硬幣皆無限供應，請問最少用幾個硬幣可以湊齊指定金額x？(以下的範例中都保證最小面額為1元，如此一來所有整數金額都可以湊齊)

對於「任兩種幣值，大幣值皆是小幣值的倍數(等價於升序排列幣值後，每一項皆是前一項的倍數)」的情況，該問題可以貪心。回想貪心的定義為「每一步驟都選擇當前最優的選擇」，對於要以最少數量的硬幣湊齊特定價值的錢，顯然優先利用大幣值的錢來湊會是較好的選擇(儘管後面會證明這件事只在前述的情況下會成立)。
假設有「1,5,10,20」這四種幣值的硬幣，要湊齊38的步驟如下。
優先換成最大面額的20元，38/20=1...18，換成1個20元剩下18元
再來換成10元，18/10=1...8，再換1個10元剩下8元
再來換成5元，8/5=1...3，再換1個5元剩下3元
再來換成1元，3/1=3，最後換3個1元，結束
得到答案38最少需要換成6個硬幣，可以證明沒有更好的解法。以下是該過程的範例程式碼。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n,m,ans=0;
    cin>>n>>m; //分別輸入不同硬幣的種類與要換的錢
    for(int i=0;i<n;i++)cin>>a[i]; //輸入不同硬幣的面額
    sort(a,a+n); //如果輸入不保證有排序，則進行排序保證能從最大的面額開始處理
    for(int i=n-1;i>=0;i--){
        ans+=m/a[i];
        m%=a[i];
    }
    cout<<ans;
}

而貪心解趨近最佳解的情況，假設有「1,3,4」三種幣值的硬幣，要湊齊6元。可以發現這個例子中就不符合上個段落的條件「任兩種幣值，大幣值皆是小幣值的倍數」。
如果同樣使用貪心，會先換成1個4元剩下2元，然後剩下部分無法換成3元，最後換成2個1元，共使用3個硬幣來湊齊6元。
但顯然直接用2個3元就能湊齊6元，所以貪心解就不是最佳解了，但可以發現在這種情況下的解仍然沒有離最佳解差太多。

但若在特別設計過的情況下，可能讓貪心解比最佳解差上許多，如「1,100,101」三種幣值的硬幣要湊齊200元，貪心解會換成1個101元與99個1元共100個硬幣，但最佳解是利用2個100元得到200元。

可以看出貪心法並不一定能得到最佳解，但演算法問題在絕大多數情況下都只要求最佳解，那麼貪心就派不上用場嗎？
事實上貪心仍有其優點，首先第一個即是符合直覺，就以上換錢的問題，多數人第一時間的反應也是先用幣值大的，在許多其他問題中，貪心法也會是最快被想到的，只不過有時候也不會特別意識到自己的解法是貪心。
第二點是能幫助思考，縱使許多情況下貪心無法得到題目要求的正確答案，但透過思考貪心在什麼情況下會得不到最佳解，也能幫助尋找替代的解決方法。
最後一點，對於貪心可以解決的題目，通常貪心會是複雜度較好的解，相較之下，許多問題尋找全域最佳解時，會需要考慮所有路徑的組合，導致複雜度多了一個以上的維度，如上述換錢問題，利用DP(動態規劃，在章節3介紹)考慮所有情況可以保證得到最佳解，但需要O(nm)的複雜度，而貪心則可以在上述特定情況下以O(n)解決。

另外這邊也強調上述講的，能用貪心得到最佳解的情況，通常可以證明其解為最佳。只不過實際使用貪心法解決問題時，一般來說不會進行嚴謹的證明，最多只是在心中進行簡單潦草的證明，或者更多時候直接直覺判斷可以貪心(或者稱作通靈)，甚至是透過AC貪心的解法來證明可以貪心(prove by AC)。