??在以往的算法課程中直砂，比如《算法導(dǎo)論》和國(guó)內(nèi)的《數(shù)據(jù)結(jié)構(gòu)和算法》幌陕，都是先講授數(shù)據(jù)結(jié)構(gòu)，然后再講算法存崖。而Algorithmic Toolbox這門系列課程另辟蹊徑，不僅是先講算法睡毒，再講數(shù)據(jù)結(jié)構(gòu)（第一門課程中講授算法来惧、第二門課程中講授數(shù)據(jù)結(jié)構(gòu)），而且是先講貪心算法演顾，再講動(dòng)態(tài)規(guī)劃（在算法導(dǎo)論中是先講動(dòng)態(tài)規(guī)劃供搀，再講貪心算法的）隅居。
??在這周的貪心算法課程中，老師講了三個(gè)例子葛虐。第一個(gè)是求長(zhǎng)途旅行需要加油的最少次數(shù)胎源。條件如下所示：
1:在滿載不加油的情況下，最多行駛400KM屿脐。
2:起點(diǎn)為A涕蚤，終點(diǎn)為B，距離為950KM的诵。
??解算法題的兩大步驟：第一步先把算法問題進(jìn)行數(shù)學(xué)建模万栅，第二步用程序表示數(shù)學(xué)建模的思想。以此題為例西疤，第一步數(shù)學(xué)建模烦粒，結(jié)果如下：
?Input: A car which can travel at most L kilometers with full tank, a source point A, a destination point B and n gas stations at distances x1 ≤ x2 ≤ x3 ≤ · · · ≤ xn in kilometers from A along the path from A to B.
?Output: The minimum number of refills to get from A to B, besides refill at A.（目標(biāo)函數(shù)）
??一共有幾種決策方式，分別是在最近的加油站加油代赁、在油量不耗盡的前提下在最遠(yuǎn)的加油站加油扰她、一直開不加油等等（例如在決策1和2之間的加油站加油）。
??決策2的具體步驟如下所示：
- Start at A
- Refill at the farthest reachable gas station G
- Make G the new A
- Get from new A to B with minimum number of refills
其中1芭碍、2义黎、3步是個(gè)循環(huán)直到結(jié)束。
??其中在貪心算法中有個(gè)核心概念是safe move豁跑，即if there exists some optimal solution in which first move is this greedy choice, then this greedy choice is called a safe move.
??在這里廉涕，證明的方式像是尋找和first move不同的情況下，最后還是等效或者不如first move的情況艇拍。在這里狐蜕，由于G是不耗盡油的最遠(yuǎn)加油站，所以除了first move選擇G以外卸夕，我們只能選擇G1层释。如下圖所示：
??在這里，其實(shí)細(xì)分的話快集，可以分為3種情況贡羔。G2>G, G2=G, G2<G。
??當(dāng)G2=G時(shí)，很顯然院溺，多加了一次油楣嘁，也就是不如的情況。
??當(dāng)G2<G時(shí)，這里也沒必要在G1地方加第一次油逐虚，也是不如的情況聋溜。
偽代碼如下所示，其中外層循環(huán)指代的是每次加油叭爱，內(nèi)層循環(huán)指代的是每次加油的具體地點(diǎn)：
A = x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn ≤ xn+1 = B
MinRefills(x, n, L)
numRefills ← 0, currentRefill ← 0
while currentRefill ≤ n:
lastRefill ← currentRefill
while (currentRefill ≤ n and x[currentRefill + 1] ? x[lastRefill ] ≤ L):
currentRefill ← currentRefill + 1
if currentRefill == lastRefill:
return IMPOSSIBLE
if currentRefill ≤ n:
numRefills ← numRefills + 1
return numRefills
