貪心演算法

語言: CN / TW / HK

引子

  • 錢幣找零問題

    假設1元、5元、10元、20元、50元、100元的紙幣分別有a,b,c,d,e,f張,現在要支付k元,至少要用多少張紙幣?

貪心演算法

貪心標準選擇: 應用當前“最好”的標準作為統一標準,將原問題變為一個相似單規模更小的子問題,而後的每一步選出來一定是原問題的最優解的一部分。(區域性最優可以推出全部最優)

使用場景:如果一個問題貪心後只剩下一個子問題且有最優子結構,就可以使用貪心演算法。

最有子結構: 當一個問題的最優解包含其子問題的最優解釋時,稱此問題具有最優子結構性質。

概念很繞啊。

解題步驟

  1. 設計資料找規律
  2. 進行貪心猜想
  3. 正確性證明
    • 一般證明: 列舉反例
    • 嚴格證明: 數學歸納和反證法
  4. 程式實現

例題(455. Assign Cookies)

假設你是一位很棒的家長,想要給你的孩子們一些小餅乾。但是,每個孩子最多隻能給一塊餅乾。對每個孩子 i ,都有一個胃口值 gi ,這是能讓孩子們滿足胃口的餅乾的最小尺寸;並且每塊餅乾 j ,都有一個尺寸 sj 。如果 sj >= gi ,我們可以將這個餅乾 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.
問題分析

用數量最小的先滿足胃口最小的,達到資源最大利用率。(先使用餅乾尺寸小的滿足胃口小的)

func findContentChildren(g []int, s []int) int {
	l1,l2 := len(g),len(s)
	if l1 || l2 == 0 {
		return 0
	}

	var res int
	for i:=0;i<l2;i++ {
		for j:=0;j<l1;j++ {
			if s[i] >= g[j] {
				res += 1
			}
		}
	}
	return res
}