貪心算法——精華入門總結(jié)...
貪心算法
英語：greedy algorithm，又稱貪婪算法，是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。
比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市，那這就是一種貪心算法。
貪心算法在有最優(yōu)子結(jié)構(gòu)的問題中尤為有效。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解。簡單地說，問題能夠分解成子問題來解決，子問題的最優(yōu)解能遞推到最終問題的最優(yōu)解。
貪心算法與動態(tài)規(guī)劃的不同在于它對每個子問題的解決方案都做出選擇，不能回退。動態(tài)規(guī)劃則會保存以前的運算結(jié)果，并根據(jù)以前的結(jié)果對當前進行選擇，有回退功能。
貪心法可以解決一些最優(yōu)化問題，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問題。在不同情況，選擇最優(yōu)的解，可能會導(dǎo)致辛普森悖論（Simpson's Paradox），不一定出現(xiàn)最優(yōu)的解。
貪心算法在Data Science領(lǐng)域都被資泛應(yīng)用，特別是金融工程。其中一個貪心算法例子就是Ensemble method
基本步驟
步驟1：從某個初始解出發(fā)；
步驟2：采用迭代的過程，當可以向目標前進一步時，就根據(jù)局部最優(yōu)策略，得到一部分解，縮小問題規(guī)模；
步驟3：將所有解綜合起來。
案例：換酒問題
題目
小區(qū)便利店正在促銷，用 numExchange 個空酒瓶可以兌換一瓶新酒。你購入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就會變成空的。
請你計算最多能喝到多少瓶酒。
示例 1
輸入：numBottles = 9, numExchange = 3輸出：13解釋：你可以用 3 個空酒瓶兌換 1 瓶酒。所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
示例 2
輸入：numBottles = 15, numExchange = 4輸出：19解釋：你可以用 4 個空酒瓶兌換 1 瓶酒。所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
分析
這道題貪心的維度非常明顯，直接暴露在題目表面，即當前喝完所有飲料后變?yōu)榭掌考由弦延锌掌亢螅?span style="font-weight: 700;color: rgb(248, 57, 41);">最大限度的、貪心的兌換飲料，依次類推，直到手上的空瓶不足以兌換出一瓶飲料止。
代碼
根據(jù)上述分析，兌現(xiàn)為代碼如下：
class?Solution(object):
????def?numWaterBottles(self,?numBottles,?numExchange):
????????"""
????????:type?numBottles:?int
????????:type?numExchange:?int
????????:rtype:?int
????????"""
????????sumb?=?numBottles
????????empty?=?numBottles
????????while?empty?//?numExchange:
????????????bottle?=?empty?//?numExchange?#?兌酒數(shù)
????????????empty?=?bottle?+?empty?%?numExchange?#?空瓶子數(shù)
????????????sumb?+=?bottle
????????return?sumb
以上就是關(guān)于貪心算法的入門介紹，給個三連，下次寫出更棒的文章。
猜你喜歡