貪心算法

1. 局部最右得到全局最右
2. 難點(diǎn)在于如何證明局部最優(yōu)可以得到全局最優(yōu)
3. 堆 和 排序 是貪心算法最常用的實現(xiàn)算法

貪心算法作為最符合自然智慧的算法，思路是從小部分取最優(yōu)從而獲得最終的最優(yōu)，但是難得是怎樣獲取部分最優(yōu)才能得到全局最優(yōu)。

有時候我們會有多個局部最優(yōu)的想法（或者說局部最貪）但是很多時候這些都是陷阱。

如何驗證我們的局部最優(yōu)想法是對的是貪心算法最復(fù)雜的地方：

1. 數(shù)學(xué)邏輯推算驗證 （太過耗時，費(fèi)力不討好）
2. 對數(shù)器驗證 （推薦）

這里推薦使用對數(shù)器來進(jìn)行驗證，即寫一個最傻的求解方法（如窮舉可能性），與我們貪心算法進(jìn)行驗證。

如何想到貪心算法 這個似乎沒有捷徑，需要閱歷經(jīng)驗和敏捷的思考，即多鍛煉吧…………

最后拋兩個例子

金條分隔問題

給一根長度為 n 的金條，分隔此金條長度為 x, y 兩份(x+y =n) 需要和金條長度數(shù)值相同的 n 個銅幣。

給定一個數(shù)組數(shù)組和為 n，問最小代價為多少。

例如：

金條長度為 80
給定數(shù)組 [50,20,10]
如果
分隔： 70 , 10 花費(fèi) 80
分隔： 50 , 20 花費(fèi) 70 總 150相對平均分割
分隔： 50 , 30 花費(fèi) 80
分隔： 20 , 10 花費(fèi) 30  總 110
最優(yōu)解

貪心思路

每次分隔盡量平均。

如何盡量平均？使用小根堆

public static int separation(int[] arr, int length) {int sum = 0;if (arr == null) {return 0;}Queue<Integer> queue = new PriorityQueue<>();for (int num : arr) {queue.add(num);}while (queue.size() > 1) {int cur = queue.poll() + queue.poll();sum += cur;queue.add(cur);}return sum;}

字符串拼接字典序最小問題

給定字符數(shù)組 [‘sdfsd’,‘wef’,‘sew’,‘a(chǎn)’] ，請給出該數(shù)組字典序拼接最小的結(jié)果

不想寫了，說思路吧，貪心最重要的其實就是思路，思路有了解法很簡單，基本上排序 或者 用堆 可以解決大部分問題

貪心解法是進(jìn)行排序，排序比較是根據(jù) 如果 o1 拼接 o2 > o2 拼接 o1 則 o1 放到前面

安排會議問題 ，給道 leetcode 的例題吧

1353.最多可以參加的會議數(shù)目

在所有開始時間相同的會議中，盡量選擇結(jié)束時間最小的會議，因為結(jié)束時間更大的會議在后續(xù)的日程中可選擇天數(shù)更多

比如在會議：[[1,1],[1,2],[1,3]] 這三個會議中，如果在第 1 天，應(yīng)該盡量選擇 [1,1] 這個會議，因為后面的兩個會議，分別可以在第 2 天和第 3 天選擇，選擇的范圍更廣

只有這樣選擇，才可以得到能參加更多的會議

所以，這里我們需要能快速的選擇結(jié)束時間最小的會議，而且這個最小的結(jié)束時間是動態(tài)變化的，因為參加了一個會議，就應(yīng)該排除這個會議

要高效的維護(hù)動態(tài)數(shù)據(jù)的最小值可以使用小根堆。