我們在Day 2 什麼是演算法?的時候有提到貪心法，今天要來深入了解他~

貪心演算法(Greedy Algorithm)

貪心的概念其實很簡單，就是每一步都選擇 當下 看起來最好的選擇，希望最後能得到全域最佳解
他不像其他演算法(例如DFS ) 一樣會回頭修改之前的決定，而是根據目前的情況直接做出最佳選擇

回頭看 Day 2 的例子

假設要用 1、5、10 元湊出 72 元，我們的策略是「每次都選面額最大、且不超過剩餘金額的錢幣」

(先選面額最大的10元)
剩72元 
剩62元 
剩52元
...(重複選10元,直到剩下2元)
剩2元 → 選1元 
剩1元 → 選1元 → 剩0元，完成

在這個例子裡，剛好能找到最少硬幣的解法(9個)

貪心演算法失敗經典例子

假設要用 1、 10、 16 湊出 30
一樣每次都選面額最大、且不超過剩餘金額的錢幣

剩30元，選 16 元
剩14元，選 10 元
剩4元
(一路選1元直到結束)
剩0元，完成

貪心解法用了 16+10+1+1+1+1 共6個硬幣

你發現了嗎 ? 其實用 10+10+10才是最佳解，共 3 個硬幣而已
所以局部最優不一定等於全部最優，在使用貪心法時需要注意

那到底什麼時候可以使用貪心法？

通常一個問題適合使用貪心法，需要具備以下兩個特性：

• 貪心選擇性質(Greedy Choice Property)
  每一步做出的局部最佳選擇，都能導向全域最佳解。
• 最佳子結構（Optimal Substructure）
  問題的最佳解包含其子問題的最佳解

Leetcode Assign Cookies

接下來看一題實作練習 Assign Cookies
題目敘述

每個孩子 i 都有一個胃口值 g[i]，代表能讓該孩子滿足的餅乾最小尺寸；而每塊餅乾 j 都具有尺寸 s[j]。如果 s[j] >= g[i]，我們就可以把餅乾 j 分發給孩子 i，該孩子就會得到滿足。你的目標是最大化能夠被滿足的孩子數量，並輸出這個最大值。

範例測資

#input
g = [1,2,3]
s = [1,1]

#output
1

可以觀察到:
胃口 1 的小孩需要至少大小為 1 的餅乾
胃口 2 的小孩需要至少大小為 2 的餅乾
胃口 3 的小孩需要至少大小為 3 的餅乾

1 -> 滿足胃口 1 的小孩
剩下另一塊大小為 1 的餅乾，無法滿足胃口 2 或胃口 3 的小孩，因此最後只有 1 個孩子被滿足，所以輸出 1

我們先將小朋友和餅乾排序過 (用sort)，這樣能確保不會有浪費的情況
例如 大小為 3 的餅乾給胃口 1 的小朋友，會浪費較多資源
sort過後，我們能確保第一個比較的一定是最小的，後面再滿足胃口較大的小朋友

題目講到當 s[j] >= g[i]時，小孩能被滿足，所以這時候能繼續檢查下一個
由於後面的小孩胃口只會更大，因此這塊餅乾不可能滿足任何剩餘的小孩，只能捨棄。
因此只需要移動餅乾指標 j (j++)

程式碼

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int i = 0; // 小孩 
        int j = 0; // 餅乾 
        int ans = 0;
        while ( i<g.size()&&j<s.size() ){ 
            if ( g[i]<=s[j] ){ 
                ans++; 
                i++; 
                j++; 
            }else{ 
                j++; 
            } 
        } 
        return ans; 
    }
};

時間複雜度

• 排序小孩(n個) O(n log n)
• 排序餅乾(m個) O(m log m)
• 遍歷 O(n + m)
  - while (i < g.size() && j < s.size())
  i 最多走 n 次 j 最多走 m 次，所以是 O(n + m)

參考資料和書籍

1. https://guide.ntucpc.org/GreedyAlgorithm/intuitive_greedy/