貪心算法的思想

貪心算法的思想

貪心算法的基本思想是找出整體當中每個小的局部的最優解，并且将所有的這些局部最優解合起來形成整體上的一個最優解。是以能夠使用貪心算法的問題必須滿足下面的兩個性質：

1.整體的最優解可以通過局部的最優解來求出；

2.一個整體能夠被分為多個局部，并且這些局部都能夠求出最優解。使用貪心算法當中的兩個典型問題是活動安排問題和背包問題。

 在對問題求解時，總是作出在目前看來是最好的選擇。也就是說，不從整體上加以考慮，它所作出的僅僅是在某種意義上的局部最優解（是否是全局最優，需要證明）。

特别注意： 若要用貪心算法求解某問題的整體最優解，必須首先證明貪心思想在該問題的應用結果就是最優解！！

以經典的活動安排為例：

1、若A是E的最優解，那麼E-A 也是問題的最優解，在餘下的問題裡，繼續拿最早結束的；

2、拿可以開始的最早結束。(是以要按結束時間排序一次，然後把可以開始的選擇上，然後繼續向後推)

貪心子結構是獨立的（往往用标志判斷而已），不同于動态規劃（後面每一邊的計算要用到前一步的值，另外開辟空間來儲存）

 貪心算法的基本步驟 ：

1、從問題的某個初始解出發。

2、采用循環語句，當可以向求解目标前進一步時，就根據局部最優政策，得到一個部分解，縮小問題的範圍或規模。

3、将所有部分解綜合起來，得到問題的最終解。