一、貪心演算法
- 是一種在每一步都採前當下看起來最好的選擇的一種策略。
- 由於是當下看起來最好的選擇，故也有可能選到錯的路線，導致最終的答案不是最佳解。
- 先舉個生活中常見的例子：
- 今天小明的撲滿裡存滿了大大小小的1塊、5塊跟10塊，今天小明打算要要幫撲滿瘦身，令它的重量降低，那麼小明可以到銀行換鈔，將幣值小、重量重的硬幣集結起來換成幣值大、重量輕的紙鈔。
- 用貪心演算法的思維，我們一定是從幣值大的 1000 開始換起，再來 500、100、50、10，以此類推，有多少換多少。
// vector<int>& nums = {1000, 500, 100, 50, 10, 5, 1};
vector<int> coinChange(vector<int>& nums, int money) {
vector<int> res(nums.size(), 0);
for (int i = 0; i < nums.size(); i++) {
res[i] += (money / nums[i]);
money %= nums[i];
}
return res;
}
- 但若我們新增了一個幣值是
23，那麼上面這個思路就有可能會導致錯誤。
- 貪心演算法的特點
- 直覺且快速
- 通常不是最佳的
- 需要會被要求證明
- always stays ahead：跑者每個時間點都在第一名，最後結果會是第一名
- exchange argument
- 用反證法，找到原解的 inversions，並作交換，證明交換後並不影響最佳解。
二、貪心演算法的應用
0. 核心思維
- 貪心演算法是從某一個初始狀態出發，每次通過選取區域性最優解向目標前進，並最終期望取得整體最優解的一種演算法。由這個定義可知，貪心選擇標準就是選擇當前最好的決策，貪心演算法根據這個標準進行決策，將原問題變成一個相似但規模更小的子問題，而後每一步選出來的一定是原問題整體最優解的一部分。
如果一個問題貪心後只剩下一個子問題且有最優子結構，那麼該問題就可以使用貪心演算法。當一個問題的整體最優解包含其子問題的最優解時，我們稱次問題具有最優子結構性質。
- 解題一般步驟
- 設計資料結構並找規律
- 進心貪心猜想
- 正確性證明(歸納法證明或是列舉反例進行反證)
- 實現程式碼
1. 找零錢問題(Coin Change)
- 先用剛剛提到的那一題來試做：
- 以貪心法的思維來做就是，幣值愈大先換，換到不能再換時再往次大的幣值換。
vector<int> coinChange(vector<int>& nums, int money) {
vector<int> res(nums.size(), 0);
for (int i = 0; i < nums.size(); i++) {
res[i] += (money / nums[i]);
money %= nums[i];
}
return res;
}
- 以範例
nums = {1000, 500, 100, 50, 23, 10, 5, 1}，money = 1069 來測試看看，以上述得到的結果應該是：(參考例題Leetcode 322. Coin Change)
{1000, 500, 100, 50, 23, 10, 5, 1} = {1, 0, 0, 1, 0, 1, 1, 4}，也就是說，得到的硬幣總數是 8(假設所有幣值都是硬幣)。- 因為夾雜了
23，使得問題變得稍微有點不一樣，因為最佳解可以是：
{1000, 500, 100, 50, 23, 10, 5, 1} = {1, 0, 0, 0, 3, 0, 0, 0}，總數 4。
- 從上面此例來觀察，貪心法是需要有適用時機的，當今天少掉
23 的時候，使用貪心法是可以得到最佳解的，因為所有數字互為因數、倍數關係，也就是說，當今天可以用 1 張 1000 解決的情況，必定可以用其它幣值用更多的代價來替換，如 2 張 500，或 10 張 100。但是 23 可以替換的是 2 個 10 塊加上 3 個 1 塊。用數字為例的話如下
- \(\boxed{\begin{array}{ll}
1069&=1\times1000+1\times50+1\times10+1\times5+4\times1\\
&=1\times(2\times500)+1\times50+1\times10+1\times5+4\times1\\
&=1\times(10\times100)+1\times50+1\times10+1\times5+4\times1\\
&=1\times(20\times50)+1\times50+1\times10+1\times5+4\times1\\
\end{array}}
\)
- 不管怎麼換，總數都是變大。
- 如果要解出上述的最佳解，需要做一點修正，或是使用暴力破解法，例如
bfs 來遍歷所有情形來獲得最小值。
- 試想要怎麼改寫可以使貪法仍然可以適用，「將23拿掉」那麼貪心法就仍可以適用，那要怎麼有技巧的將
23 拿掉呢。
23 能夠有效的替換表示我們一定會使用到 23，也就是說我們可以找到反例使 23 不能有效的替換就好了。
23 = 23*1(1) 換 10*2 + 1*3(5)46 = 23*2(2) 換 10*4 + 5*1 + 1*1(6)69 = 23*3(3) 換 50*1 + 10*1 + 1*4(6)92 = 23*4(4) 換 50*1 + 10*4 + 1*2(7)115 = 23*5(5) 換 100*1 + 10*1 + 5*1(3)
- 我們可以發現當
23 替換到第 5 個的時候已經不能有效的替換了，表示我們只有嘗試替換 0~4 個 23 硬幣，其餘剩下的錢用貪心法去計算，仍然可以得到有效的解。(在此只是為了展示失去「局部最佳性」的範例，不做嚴謹的數學證明)
- 即求
min(f(1069)+0, f(1046)+1, f(1023)+2, f(1000)+3, f(976)+4。
vector<int> coinChange(vector<int>&nums, int money) { ... } // implement by greedy
vector<int> coinChangePlus(vector<int>&nums, int money) {
vector<int> res;
int coins = INT_MAX;
for (int i = 0; i <= 4; i++) {
vector<int> tmp = coinChange(nums, money-23*i);
tmp[4]+=i;
int cnt = accumulate(tmp.begin(), tmp.end(), 0);
if (cnt < coins) {
res = tmp;
coins = cnt;
}
}
return res;
}
- 以上方法當遇到單一奇異數(無因倍數關係)的時候還可以用，但遇到多個奇異數的時候，複雜度就會明顯上升，到時後我們會遇用其它方法來解構。在後面的動態規劃篇，有深入的介紹，如何利用其它技巧達到剪枝得到最佳解。
- 由此可發現，貪心法不一定會得到最佳解，需要嚴格的驗證「局部最佳性」，才能保證最後的解是最佳解。
2. 背包問題(Knapsack Problem)
- 常見的背包問題分為分數背包問題與0-1背包問題。
- 今天在某個場合，你有一個載重5kg的背包，面前有3kg的金沙、3kg的銀沙與2kg的銅沙，已知金的價格比銀高，銀的價格比銅高。你可以任意決定怎麼將它們裝進背包，最後換取對應價值的獎金，試問怎麼裝可以得到最高的獎金？
- 同樣的場合，金沙、銀沙、銅沙換成了金塊、銀塊、銅塊，分別也是 3kg、3kg、2kg，且不可切割，試問要怎麼裝可以得到最高的獎金？
- 第1題(分數背包)，顯而易見，用貪心法來做一定是盡可能先裝滿價值高的金沙，再用剩餘的空間以此類推裝填其它的。(3kg金沙+2kg銀沙)
- 第2題(0-1背包)，由於拿完金塊，無法再拿銀塊，所以最佳解變成了拿金塊與銅塊。(3kg金塊+2kg銅塊)
三、例題
1. 餅乾分配問題
- Leetcode 455. Assign Cookies
- 有若干個不同份量的餅乾，與若干個需要不同份量才能滿足的小孩，試問餅乾最多可以讓幾個小孩滿意。
- 把餅乾的份量從小排到大，把小孩從需求小排到需求大。
- 盡可能的滿足需求小的小孩。(若需求小的都滿足不了，那麼需求大的就不可能滿足了)
int findContentChildren(vector<int>& children, vector<int>& cookies) {
sort(children.begin(), children.end());
sort(cookies.begin(), cookies.end());
int child = 0, cookie = 0;
while (child < children.size() && cookie < cookies.size()) {
if (children[child] <= cookies[cookie]) child++;
cookie++;
}
return child;
}
2. 股票買賣問題
3. 跳躍遊戲