貪婪算法的解題思路
[toc]
本來想叫《貪婪算法的設(shè)計思想》的猬仁，但是覺得寫的不夠深靶病，純粹以解題為目的的復(fù)習(xí)還是不要這么寫好溃睹。
貪婪法顷啼，又稱貪心算法踏枣，是尋找最優(yōu)解問題的常用方法，方法模式是在求解過程的每個步驟應(yīng)用貪心原則：
每個步驟選取當(dāng)前狀態(tài)下最好的或最優(yōu)的選擇（局部最有利選擇）
問題：最后堆疊的結(jié)果不一定是最優(yōu)解
以題為例：
1.找零錢
有25分钙蒙、10分、5分间驮、1分四種硬幣躬厌，對于輸入 x ，輸出最少找錢數(shù)的找錢方案竞帽。例如：
輸入：41
輸出：25 10 5 1
這個問題使用貪婪法可以得到最優(yōu)解扛施，即每一步選擇小于剩余應(yīng)找錢數(shù)的最大硬幣。（剩余應(yīng)找錢數(shù) = x - 已找錢數(shù)）
但是如果將硬幣設(shè)置為 25分屹篓、20分疙渣、5分、1分 四種硬幣堆巧，
這個時候最優(yōu)解是：20 20 1妄荔，
但是貪婪法結(jié)果是：25 5 5 5 1.
2.背包問題
有 N 件物品和一個承重為 C 的背包泼菌，每件物品的重量是 wi，價值是 pi啦租，求將哪幾件物品放入背包可以使重量不超過 C 的情況下總價值最大哗伯。
設(shè)置一個價值系數(shù)，Vi = pi / wi篷角，那么就又變成一個找零錢問題焊刹，在價值系數(shù)中挑選最大項并計算剩余的可承重量。
總結(jié)
大多數(shù)情況下恳蹲，貪婪法只能得到比較接近最優(yōu)解的近似的最優(yōu)解虐块。可作為一種輔助思想嘉蕾，但在一般解題的過程中需要慎重一點贺奠。
貪婪法思想的典型應(yīng)用：最小生成樹的 Prim 算法和 Kruskal 算法，Dijkstra 的單源最短路徑算法
Dijkstra 為例：
1.獲取所有源點可達(dá)的直接路徑長度（不能直接到達(dá)的設(shè)為∞）設(shè)為 dis[];
2.找到離源點最近的一個頂點荆针，以其為拓展敞嗡，得到以其為中間點的可達(dá)最短路徑，并更新 dis[];
3.在未拓展過的頂點中重復(fù)步驟2航背，最后得到源點到其他點的所有最短路徑喉悴。
關(guān)于怎么正確的解決0-1背包問題，請看：動態(tài)規(guī)劃-0-1背包問題
