貪心算法是什麽？貪心算法如何解決問題？

你可能不知道貪心算法，但你一定知道活在當下。如果你知道，那麽(me) 恭喜你，你已經掌握貪心算法的核心本質了！

貪心算法的理念就是不問過去，不計將來，隻考慮當下。撿了芝麻丟(diu) 了西瓜？不存在的！當下有西瓜，絕不碰芝麻~

貪心算法講究的是每遇到一個(ge) 子問題， 都取當下情況的最優(you) 解， 直到所有子問題被解決(jue) 。

那麽(me) ，貪心算法到底是怎麽(me) 幫我們(men) 解決(jue) 問題的呢？

我購買(mai) 了一張戛納電影節的一日票。雙程機票、翻倍的酒店價(jia) 格都讓我的錢包越來越扁... 心痛 .jpg... 為(wei) 了能最大限度薅到資本主義(yi) 的羊毛，我當然會(hui) 爆發出愛因斯坦的智商，來精準計算怎樣的觀影順序能讓我在有限的時間裏看到最多的電影！傳(chuan) 奇天主教總統傳(chuan) 記《肯尼迪傳(chuan) 》，小李子《花月殺手》，北野武的《首》還有纏繞三角戀《燃東(dong) 》-- 統統到我碗裏來！！

假設：當天有 n 部電影，第 i 部電影在 a 時開始、b 時結束。每部電影我都可以選擇看或不看。但如果我選擇看某部電影，那即使遇到爛片也必須全程看完。並且我不能同時觀看 2 部及 2 部以上電影。

求：我最多能看幾部電影？

很顯然，這道題的子問題就是：從(cong) 某個(ge) 時刻起，應該如何選擇下一場電影？

我可以有以下選擇：

1、當天每次都選開始時間最早的電影；

2、當天每次都選結束時間最早的電影；

3、當天每次都選用時最短的電影；

4、當天每次都選與(yu) 最少可選工作有重疊的電影。

根據以下圖示，很容易證明選擇 1，3，4 是不可行的！

由此可見，子問題的最優(you) 解就是：每次都選結束時間最早的電影！

這就是此題的貪心策略，可選電影中結束時間最早的那場電影就是本題的局部最優(you) 解。

由於(yu) 每場電影包含一個(ge) 開始時間和一個(ge) 結束時間，所以我們(men) 可以定義(yi) 一種結構體(ti) ，命名為(wei) Movie。

Movie 中包含了開始時間和結束時間，代碼如下：

總結：

• 貪心法就是指在求解問題時，總是做出當前最好的選擇（而不是整體）。
• 貪心算法沒有固定的框架，算法設計的關鍵是貪心策略的選擇。
• 貪心策略必須具備無後效性，即某個狀態的選擇隻與當前狀態有關。

小課堂

在我看來，每個(ge) 人每天都在做“貪心算法”。

我們(men) 的人生都是由無數個(ge) 子問題構成的，我們(men) 需要在無數個(ge) 小的路口做出我們(men) 認為(wei) 對的選擇，但生活無法回頭，即使後來我們(men) 知道我之前的選擇可能並非最優(you) 解，可我們(men) 也無法從(cong) 頭來過。沒有人可以穿越回去修改過去的選擇，從(cong) 而獲得“全局的絕對最優(you) 解”。

因為(wei) 我知道我永遠隻能基於(yu) 當下的認知水平，在不完美的條件下做我認為(wei) 最利於(yu) 當下的選擇，而不是在理想情況下做最優(you) 解，抱怨“為(wei) 什麽(me) 條件不完美”是沒有意義(yi) 的。不完美是人生的常態，我能做到的，隻有不埋怨現狀，不害怕未來，盡量不斷地做出我認為(wei) 對的選擇。

不要將自己困囿於(yu) 過去的錯誤中，也不要懼怕未來，抓住每一個(ge) 小時做貪心算法吧！