本文通過一道經典的貪心演算法題（leetcode 455. 分發餅干）來介紹貪心演算法，供大家參考，希望能對大家了解貪心演算法提供幫助，
題目
假設你是一位很棒的家長，想要給你的孩子們一些小餅干，但是，每個孩子最多只能給一塊餅干，
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] ，如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足，你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值，
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3，雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足，所以你應該輸出1，
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2，你擁有的餅干數量和尺寸都足以讓所有孩子滿足，所以你應該輸出2.
解題思路
以示例 2 為例，如下圖示，其中 size 和 greedy 分別表示餅干尺寸和小朋友的貪心指數，由于數量比較少，直接就可以看出將 size 為 1 的餅干分給 greedy 為 1 的小朋友，將 size 為 2 的餅干分給 greedy 為 2 的小朋友，就可以小朋友開心（滿足其胃口），但是當餅干很多或者小朋友時，就不能輕易看出分配策略了，
有什么方法能讓更多的小朋友開心呢？可以嘗試讓size 最大的餅干去滿足最貪心的小朋友，如果能滿足則留給次貪心的小朋友的餅干將是當前最大的餅干（如下圖示），如果不能滿足，則所有的餅干都無法滿足這位最貪心的小朋友，雖然不能讓這位小朋友開心了，但是已經盡最大可能讓其開心了，此時只能嘗試讓最大的餅干去滿足次貪心的小朋友，這樣相當于每次嘗試都優先使用當前剩下的最大的餅干，留給后面的小朋友的也相應的是最大的餅干，能夠最大程度地保證讓最多的小朋友開心，
因為要涉及到當前最大的餅干尺寸以及小朋友們當前的最大胃口值，所以需要對 size 和 greedy 這兩個陣列排序，然后嘗試用當前 size 的最大值去滿足當前最貪心的小朋友，
Show me the Code
更多精彩
關注公眾號 『 TanLiuYi00 』，關注后回復【演算法】即可獲取高清無碼的經典演算法電子
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260899.html
標籤：其他
下一篇：網路層的核心功能