本文主要作為自己的學習筆記幸缕，并不具備過多的指導意義直焙。
概述
貪心算法通常用來求解最優(yōu)問題
-
由局部最優(yōu)解到整體最優(yōu)解
通過不斷對局部最優(yōu)進行操作敌土，最終達到整體最優(yōu)
-
無后效性
后序操作浴滴，不會出現(xiàn)數(shù)據(jù)狀態(tài)的回滾
-
和DP(動態(tài)規(guī)劃)之間的聯(lián)系
很多貪心問題可以通過DP進行求解
最優(yōu)裝載問題
- 給出N個物體哥桥，第一個物體重量為Mi
- 盡量選擇最多的物品，總重不超過C
先將物品按照質(zhì)量排序狸捅，然后依次放入每個物品衷蜓，直到總重量將超過C位置。
這里依次將剩余物品中質(zhì)量最小的物品放入的過程尘喝，就是貪心的過程磁浇。
合并果子
一類總過程代價，取決于子過程代價的問題
- 有N堆果子朽褪，沒堆果子的數(shù)量為Ai置吓，每次可以將兩堆果子合并无虚，每次合并將消耗兩堆果子總數(shù)的體力。
- 求最小消耗的體力
- 1<N<10000
首先衍锚，如果我們什么都不管直接兩兩合并：總計消耗48點體力
然后友题，我們嘗試排序后兩兩合并：總計消耗44點體力
最后，我們嘗試只將當前所有數(shù)據(jù)中最小的兩個進行合并：總計消耗38點體力
解法
構(gòu)建一個小根堆戴质，每次從堆頂推出兩個元素合并度宦。并且將合并都的元素追加進小根堆中即可。
具體證明的過程有一定難度告匠，可以參考哈夫曼編碼證明的過程戈抄。
以上的操作過程，也就是貪心的過程后专。他只保證單次合并所消耗的體力最優(yōu)划鸽，而不在意其他的數(shù)據(jù)該如何合并。
堆結(jié)構(gòu)往往用來解決貪心的問題行贪。因為貪心問題往往需要一個明確的指標漾稀，最大值或者最小值。
項目利潤
輸入：
cost[]：每個項目的花費
profits[]：每個項目的利潤（純利潤）
k：最多能做k個項目
w：表示初始資金
輸出：
最后可以獲得的最大錢數(shù)
說明：一次只能做一個項目建瘫，且做完一個之后馬上就能獲得收益崭捍，可以支持做下一個項目
- 將
cost與profits中的元素依次合并成一個新的節(jié)點node:
public class Node {
public var c :Int //項目花費
public var p :Int //項目利潤
public init(cost:Int,profit:Int) {
self.c = cost
self.p = profit
}
}
- 準備一個以
項目花費構(gòu)建的小根堆
將所有node依次放入
- 準備一個以
項目利潤構(gòu)建的大根堆
貪心過程:
-
從小根堆中依次彈出堆頂元素，直到
node.c>w(項目所需資金大于當前資金)具體代碼上啰脚，將
小根堆數(shù)組removeFirst殷蛇，然后將arr[0]與arr[arr.count-1]位置交換。讓小根堆對arr[0]位置元素向下調(diào)整即可橄浓。 -
將小根堆中彈出的元素放入大根堆中(大根堆中即為當前可執(zhí)行的項目)
具體代碼上粒梦，將元素追加進大根堆數(shù)組末尾，并進行調(diào)整即可荸实。
-
從大根堆中彈出堆頂元素匀们，并將
w += node.p(執(zhí)行收益最大的項目，并且更新當前資金)具體代碼上與第一步類似
該貪心過程總計執(zhí)行k次准给，每一次執(zhí)行都只需要關(guān)心小根堆中最小值泄朴，與大根堆中最大值即可。最后的w即為最大總資產(chǎn)露氮。
會議安排
在優(yōu)先的時間內(nèi)安排數(shù)量最多的會議
做一張圖可以直觀表示過程:
我們將藍色表示為待安排祖灰，紅色表示為已安排，黑色表示為不可安排
我們可以嘗試幾種不同的貪心策略
- 每次選擇持續(xù)時間最短的安排
顯然不可行
- 每次選擇開始時間最早的
顯然也不可行
- 每次選擇開始時間最早的并且持續(xù)時間最短的來安排
由此可見該方案是可以行的
代碼也很簡單畔规，只需要關(guān)心當前有效數(shù)據(jù)內(nèi)開始時間晚于當前會議結(jié)束時間的結(jié)束時間最早的一個數(shù)據(jù)即可局扶。
func bestArrange(programs:[Program]) -> Int {
program.sort("end")//根據(jù)program.end進行排序
var res = 0
var current = 0
for p in programs {
if p.current > current { //開始時間晚于當前時間，否則作廢
res += 1
current = p.end //開會，當前時間變成會議結(jié)束時間
}
}
return res
}
貪心策略的證明
貪心策略的數(shù)學證明通常很復雜三妈，有能力可以去翻閱
這里推薦一種很方便的方式畜埋，對數(shù)器。
通過小樣本大樣本量的測試畴蒲，證明貪心策略的正確性由捎。
以排序算法的證明舉例
var checkOK = true
for i in 0..<10000 {
var arr1 = generateRandomArray(size: 5, value: 20) //獲取一個長度為10，最大值為20的隨機數(shù)數(shù)組
var arr2 = arr1 //數(shù)組在swift里屬于值類型饿凛，賦值動作會自動copy
let originalArr = arr1
arr1.sort()//一定正確的算法
radixSort(arr: &arr2, maxDigit: 2)
if arr1 != arr2 {
checkOK = false
print(originalArr)
print(arr2)
break
}
}
print(checkOK ? "比對成功":"比對失敗")
對于貪心問題，可能不一定存在一個一定正確的算法软驰。那么我們完全可以不去比對結(jié)果是否一致涧窒，只要貪心策略的結(jié)果永遠優(yōu)于默認順序得出的結(jié)果即可。
關(guān)于對數(shù)器的介紹可以參閱另一篇
