Алгоритм жадного выбора: когда локальный оптимум не гарантирует глобальное решение

我們在Day 2 什麼是演算法?的時候有提到貪心法，今天要來深入了解他~ 貪心的概念其實很簡單，就是每一步都選擇 當下 看起來最好的選擇，希望最後能得到全域最佳解 他不像其他演算法(例如DFS ) 一樣會回頭修改之前的決定，而是根據目前的情況直接做出最佳選擇 假設要用 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 個硬幣而已 所以局部最優不一定等於全部最優，在使用貪心法時需要注意 通常一個問題適合使用貪心法，需要具備以下兩個特性： 接下來看一題實作練習 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; } }; 時間複雜度 while (i < g.size() && j < s.size()) 參考資料和書籍