發(fā)現(xiàn)藍橋杯上好多題目涉及到貪心，決定學一學。

貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說：不從整體最優(yōu)上考慮，而是在某種意義上的局部最優(yōu)解。其關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關(guān)。

貪心選擇

貪心選擇是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。貪心選擇是采用從頂向下、以迭代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終能得到問題的最優(yōu)解。通常可以首先證明問題的一個整體最優(yōu)解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學歸納法證明，通過每一步貪心選擇，最終可得到問題的一個整體最優(yōu)解。

最優(yōu)子結(jié)構(gòu)

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運用貪心策略在每一次轉(zhuǎn)化時都取得了最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法或動態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對結(jié)果產(chǎn)生直接影響，而動態(tài)規(guī)劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態(tài)規(guī)劃則會根據(jù)以前的選擇結(jié)果對當前進行選擇，有回退功能。動態(tài)規(guī)劃主要運用于二維或三維問題，而貪心一般是一維問題?。

思想

貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進行，根據(jù)某個優(yōu)化測度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個數(shù)據(jù)，他的選取應該滿足局部優(yōu)化的條件。若下一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止。

過程

建立數(shù)學模型來描述問題；

把求解的問題分成若干個子問題；

對每一子問題求解，得到子問題的局部最優(yōu)解；

把子問題的解局部最優(yōu)解合成原來解問題的一個解。

貪婪算法可解決的問題通常大部分都有如下的特性：

• 隨著算法的進行，將積累起其它兩個集合：一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象。
• 有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答。該函數(shù)不考慮此時的解決方法是否最優(yōu)。
• 還有一個函數(shù)檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性。
• 選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。
• 最后，目標函數(shù)給出解的值。
• 為了解決問題，需要尋找一個構(gòu)成解的候選對象集合，它可以優(yōu)化目標函數(shù)，貪婪算法一步一步的進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮；否則就加到集合里。每一次都擴充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優(yōu)的。

轉(zhuǎn)載于:https://www.cnblogs.com/panweiwei/p/6541159.html

總結(jié)

以上是生活随笔為你收集整理的C语言 · 贪心算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。