貪婪算法意味著在解決問題時，總是做出當前最佳的選擇。也就是說，我們不考慮全局優化，而只做出某種意義上的局部最優解。貪婪算法不可能得到所有問題的整體最優解，但關鍵是貪婪策略的選擇，它必須沒有後效，即某個狀態之前的過程不會影響後來的狀態，而只與當前狀態有關。
解決問題的壹般步驟是:
1.建立描述問題的數學模型；
2.把解決的問題分成幾個子問題；
3.求解每個子問題得到子問題的局部最優解；
4.將子問題的局部最優解合成原問題的解。
如果妳對動態編程有更多的了解，妳會發現它們之間的相似之處。大多數最優解問題可以分成子問題。如果將解空間的遍歷視為子問題樹的遍歷，則可以通過以某種形式遍歷整個樹來獲得最優解，這在大多數情況下是不可行的。貪婪算法和動態規劃本質上都是對子問題樹的修剪。兩種算法都要求問題具有子問題最優性的性質（構成最優解的每個子問題的解對於子問題本身來說肯定是最優的）。動態規劃法代表了這類問題的壹般解法。我們自下而上地構造子問題的解，找到每個子樹的根下面的每片葉子的值，並將最優值作為自己的值，並丟棄其他值。貪婪算法是動態規劃方法的壹個特例，它可以證明每個子樹的根的值不依賴於下面葉子的值，而只依賴於當前問題。換句話說，可以在不知道節點的所有子樹的情況下找到該節點的值。由於貪婪算法的這壹特性，它不需要自下而上地遍歷解空間樹，而只需要從根開始，選擇最佳路徑並壹路走下去。
話不多說，我們來看幾個具體的例子慢慢了解壹下:
1.活動選擇問題
這是算法導論中的壹個例子，也是壹個非常經典的問題。有n個活動需要在同壹天使用同壹個教室，a1，a2，…，an，教室壹次只能由壹個活動使用。每個活動ai都有開始時間si和結束時間fi。壹旦被選擇，活動的ai將占據半開時間間隔【si，fi】。如果【si，fi】和【sj，fj】不重疊，則可以在這壹天安排兩個活動ai和aj。問題是如何安排這些活動，以使盡可能多的活動在不沖突的情況下舉行。例如，下圖所示的活動集，其中活動根據結束時間單調遞增地排序。
考慮使用貪婪算法來解決問題。為了方便起見，我們使用不同顏色的線條來表示每個活動。線的長度是活動占用的時間段，藍線代表我們選擇的活動。紅線表示我們沒有活動選擇。如果我們每次都選擇開始時間最早的活動，我們無法獲得最優解:
如果我們每次都選擇持續時間最短的活動，我們無法獲得最優解:
通過數學歸納法可以證明，我們的貪婪策略應該是每次選擇結束時間最早的活動。直觀上也很好理解。以這種方式選擇兼容的活動可以為未計劃的活動留出盡可能多的時間。這也是活動根據結束時間以單調和遞增的順序排序的原因。
#包含& amplt；cstdio & ampgt；
#包含& amplt；iostream & ampgt；
#包含& amplt；算法與數學。gt；
使用命名空間std
int N；
結構法案
{
int start
int end
} act【100010】；
布爾cmp（第壹幕，第二幕）？
{
返回a.end & amplt；b.end？
}
int greedy _ activity _ selector（）？
{
int num=1，I = 1；
for（int j = 2；強生公司。lt；= N；j++)
{
如果（行為【j】。開始& ampgt；第壹幕。結束)
{
I = j；？
2.硬幣兌換問題
這個問題在我們的日常生活中比較常見。假設有C0、C1、C2、C3、C4、C5和C6鈔票，分別為1元、2元、5元、10元、20元、50元和100元。現在，我應該用多少張鈔票來支付K元？用貪婪算法的思想，顯然每壹步都可以盡可能用大面值的紙幣來完成。我們在日常生活中自然也是這樣做的。在程序中，值已經預先按從小到大的順序排列。
}
3.再論背包問題
從頭開始學習動態編程
我們已經討論了三個基本的背包問題:零壹背包、部分背包和完全背包2。很容易證明貪婪算法不能解決背包問題。然而，我們考慮這樣壹個背包問題:當選擇要放入背包的物品I時，我們可以選擇物品的壹部分，但不壹定是全部。這時，妳可以使用貪婪算法來解決它。計算每個物品的單位重量值作為貪婪選擇的基礎指標，選擇單位重量值最高的物品，將盡可能多的物品放入背包中，並繼續此策略直到背包裝滿。貪婪選擇在零壹背包問題中得不到最優解的原因是貪婪選擇不能保證背包最終能裝滿，部分閑置的背包空間降低了每公斤背包空間的價值。在程序中，單位重量值已預先按從大到小的順序排列。
}
4.多機排序問題由n個工件組成的工件集可以由m臺相同的機器加工。要求給出壹個作業調度方案，使得給定的n個作業能在盡可能短的時間內被m臺機器處理。該作業不能拆分成更小的子作業；每項工作都可以在任何機器上進行。這個問題是NP完全的，沒有有效解（尋找最優解），但可以通過貪婪選擇策略設計壹個更好的近似算法（尋找次優解）。當n
5.POJ1700是壹個經典的貪婪算法示例。題目大意是只有壹條船，可以坐兩個人。小船的速度比那兩個人的速度慢。之後，需要壹個人把船劃回來，問運送N個人到對岸需要多長時間。首先，所有人過河所需的時間按升序排序。我們考慮把最需要時間獨自過河的兩個旅行者送到對岸。有兩種方法:1。最快和第二快的渡河，然後最快的劃船回來；第二慢和最慢的人過河，然後第二快的人劃船回來，所需時間為:t【0】+2 * t【1】+t【n-1】；2.過河最快和最慢，然後劃船最快回來，過河最快和第二慢，然後劃船最快回來。所需時間為:2 * t【0】+t【n-2】+t【n-1】。如果妳計算壹下，妳就會知道其他情況需要更多的時間。每次在不影響他人的情況下運送這兩個人花費的時間最長。這個問題具有貪婪底層結構的性質。交流代碼:
}
6.區間覆蓋問題POJ1328是貪婪算法的壹個經典例子。題目的主旨是假設海岸線是壹條無限長的直線。陸地在海岸線的壹邊，而海洋在另壹邊。每個小島都是海洋中的壹個點。雷達位於海岸線上，只能覆蓋D的距離，因此如果可以覆蓋島嶼，則它們之間的距離最多為D .題目要求計算可以覆蓋所有給定島嶼的最小雷達數量。對於每個島嶼，我們可以計算雷達定位的間隔。
問題是如何用盡可能少的點覆蓋這些區間。首先，根據左端點的大小對所有區間進行排序，並且最初需要壹個點。如果兩個區間相交且不重疊，我們不需要做任何事情；如果壹個區間完全包含在另壹個區間中，我們需要更新區間的右端；如果兩個區間不相交，我們需要添加點並更新右側終點。交流代碼:
//按間隔的左端排序
雙s =點【0】。y；
//間隔的右端
for（int I = 1；我& amplt；n；i++)
{
如果（點【I】。x & ampgt；s)
//如果兩個部分不重疊，則增加雷達的數量並更新右端點。
{
計數++；
s =點【I】。y；
}
else if（點【I】。y & amplt；s)
//如果第二個區間完全包含在第壹個區間中，則更新右端點。
{
s =點【I】。y；
}
}
}
cout & amplt；& amplt；《案例》。lt；& amplt；num & amplt；& amplt；:‘& amp；lt；& amplt；‘& amp；lt；& amplt；計數& amplt；& amplt；endl
num++；
}
}
7.銷售競賽中在學校OJ中完成的壹個好問題，請在此處編碼。假設甚至有幾天，妳每天都必須購買或出售壹件物品。妳只能選擇壹種操作，而且必須選擇。起初，妳沒有這樣壹個項目。現在我給妳每天的商品價格表，請妳計算最大收入。首先，我們必須明白，我們必須在第壹天購買，在最後壹天出售，最後手頭壹無所有。然後我們每次取除第壹天和最後壹天以外的兩天時間，買小的賣大的，把賣價堆成最小堆。如果價格高於堆的頂部，則將其交換。這樣，我們確保了賣價總是大於買價，我們肯定會獲得最大的利益。
#包含& amplt；排隊和排隊。gt；
#包含& amplt；矢量與數學。gt；
#包含& amplt；cstdio & ampgt；
#包含& amplt；cstdlib & ampgt；
#包含& amplt；cstring & ampgt；
#包含& amplt；iostream & ampgt；
#包含& amplt；算法與數學。gt；
使用命名空間std
long long int price【100010】，t，n，res
int main()
{
IOs::sync _ with _ stdio（false）；
CIN & amp；gt；& ampgt；t；
while（t-）
{
CIN & amp；gt；& ampgt；n；
優先級隊列& amplt；long long int，vector & amplt；龍龍國際貿易有限公司。gt；，greater & amplt；龍龍國際貿易有限公司。gt；& ampgt；q；
RES = 0；
for（int I = 1；我& amplt；= n；i++)
{
CIN & amp；gt；& ampgt；price【I】；
}
RES-= price【1】；
RES+= price【n】；
for（int I = 2；我& amplt；= n-1；i=i+2）
{
long long int buy = min（price【I】，price【I+1】）；
long long int sell = max（price【I】，price【I+1】）；
如果(！q.empty（）
{
如果（購買& ampgt；q.top（））
{
RES = RES-2 * q . top（）+買入+賣出；
q . pop（）；
q.push（買入）；
q .推（賣）；
}
其他
{
RES = RES-買入+賣出；
q .推（賣）；
}
}
其他
{
RES = RES-買入+賣出；
q .推（賣）；
}
}
cout & amplt；& amplt；資源和服務。lt；& amplt；endl
}
}
讓我們用數據結構中的知識來解釋幾個例子。8.霍夫曼編碼這也是算法導論中的壹個例子。霍夫曼編碼是壹種廣泛應用於數據文件壓縮的非常有效的編碼方法。我們可以用多種方式表達文件中的信息。如果我們使用01字符串來表示字符，並使用固定長度編碼，則需要3位來表示壹個字符，整個文件編碼需要300000位。采用變長編碼，高頻字符編碼較短，低頻字符編碼較長，達到減少整體編碼的目的，因此整個文件編碼需要（45×1+13×3+12×3+16×3+9×4+5×）。
每個字符被賦予壹個01字符串作為其代碼，任何字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。也許無前綴代碼是壹個更好的名稱，但前綴代碼是壹個公認的標準術語。編碼的前綴性質可以使解碼非常簡單:例如，001010101可以唯壹地分解為0，0，101，11。解碼過程需要方便地取出編碼的前綴，因此可以使用二叉樹作為前綴碼的數據結構:樹葉代表給定的字符；從樹根到樹葉的路徑被用作字符的前綴碼；代碼中每壹位的0或1被用作標誌，分別指示到左邊子或右邊子的節點。
從上圖可以看出，具有最優前綴碼的二叉樹總是完全二叉樹，而具有固定長度碼的二叉樹則不是完全二叉樹。？給定編碼字符集C和頻率分布f和C，前綴碼編碼方案對應於二叉樹T .字符C在樹T中的深度記錄為dT（C），dT（C）也是字符C的前綴碼長度。平均碼長度定義為:
使平均碼長最小的前綴碼編碼方案稱為c的最佳前綴碼？霍夫曼編碼的構造方法:首先，合並頻率最小的兩個字符對應的子樹，並計算合並後的子樹的頻率；重新排序每個子樹；合並排序後的子樹序列；重復上述過程，將所有節點合並為1棵完整二叉樹；給二叉樹中的邊賦值0和1，得到每個字符的變長編碼。
POJ3253是使用這壹思想的典型例子。題目的主要思想是將壹塊無限長的木板鋸成若幹塊給定長度的小木板，每鋸壹塊都需要壹定的費用，這個費用就是目前所鋸木板的長度。給定每個所需小板的長度和小板的數量，找出最小成本。以三塊長度分別為5、8、5的木板為例:首先，從無限長的木板上鋸下長度為21的木板，花費21；然後，從長度為21的木板上鋸下長度為5的木板需要花費5英鎊。然後，從長度為16的木板上鋸下長度為8的木板需要8英鎊。總成本=21+5+8=34。利用霍夫曼的思想，為了使總成本最小化，每次只選擇兩塊長度最小的木板並將其加在壹起，然後將這些總和加到總成本中。為了提高效率，使用了優先級隊列優化，並且還使用了long long int來保存結果。交流代碼:
#包含& amplt；排隊和排隊。gt；
#包含& amplt；cstdio & ampgt；
#包含& amplt；iostream & ampgt；
使用命名空間std
int main()
{
long long int sum
int i，n，t，a，b；
while （~ scanf（“% d“，& ampampn）
{
優先級隊列& amplt；int、vector & amplt；int & ampgt；，greater & amplt；int & ampgt；& ampgt；q；
for(I = 0；我& amplt；n；i++)
{
scanf（“% d“，& ampampt）；
q . push；
}
sum = 0；
if（q . size（）= = 1）
{
a = q . top（）；
sum+= a；
q . pop（）；
}
while（q . size（）& amp；gt；1)
{
a = q . top（）；
q . pop（）；
b = q . top（）；
q . pop（）；
t = a+b；
sum+= t；
q . push；
}
printf（“% lld \ n“，sum）；
}
}
9.Dijkstra算法Dijkstra算法是由E.W.Dijkstra在1959中提出的。它是目前公認的解決最短路徑的最佳方法，前提是圖中不能有負邊。該算法解決了從單個源點到其他頂點的最短路徑問題，其主要特點是每次叠代中選擇的下壹個頂點是標記點之外距離源點最近的頂點，簡單來說就是bfs+貪婪算法的思想。
#包含& amplt；iostream & ampgt；
#包含& amplt；算法與數學。gt；
#定義INF 1000
#define MAX_V 100
使用命名空間std？
int main()
{
int V，E；
int i，j，m，n；
int cost【MAX _ V】【MAX _ V】；
int d【MAX _ V】；
bool使用了【MAX _ V】；
CIN & amp；gt；& ampgt；V & ampgt；& ampgt；e；
fill（d，d+V+1，INF）；
fill（used，used+V，false）；
for(I = 0；我& amplt；五；i++)
{
for(j = 0；強生公司。lt；五；j++)
{
if（I = = j）cost【I】【j】= 0；
else cost【I】【j】= INF；
}
}
for（m = 0；並購。lt；e；m++）
{
CIN & amp；gt；& ampgt；我& ampgt；& ampgt；強生公司。gt；& ampgt；成本【I】【j】；
成本【j】【I】=成本【I】【j】；
}
CIN & amp；gt；& ampgt；n；
d【n】= 0；
//源點
while（真）
{
int v = V
for（m = 0；並購。lt；五；m++）
{
如果((！used【m】）& amp；amp& ampamp（d【m】& amp；lt；d【v】））v = m；
}
if（V = = V）break；
used【v】= true；
for（m = 0；並購。lt；五；m++）
{
d【m】= min（d【m】，d【v】+cost【v】【m】）；
}
}
for(I = 0；我& amplt；五；i++)
{
cout & amplt；& amplt；“之間的最短距離”。lt；& amplt；n & amplt；& amplt；“和”& amplt；& amplt；我& amplt；& amplt；“是”& amplt；& amplt；d【I】& amp；lt；& amplt；endl
}
}
10.最小生成樹算法
設壹個網絡表示為壹個無向連通加權圖G =（V，E），E），E中每條邊（V，w）的權重為c【V】【w】。如果G的子圖G’是包含G的所有頂點的樹，那麽G’稱為G的生成樹..生成樹的成本是指生成樹上所有邊的權重之和。在G的所有生成樹中，代價最小的生成樹稱為G的最小生成樹..例如，在設計通信網絡時，圖的頂點用於表示城市，邊（v，w）的權重c【v】【w】用於表示建立城市v和城市w之間的通信線路的成本，最小生成樹給出了建立通信網絡的最經濟方案。
構造最小生成樹的Kruskal算法和Prim算法都利用了MST（最小生成樹）性質:設頂點集U是V的真子集（可以任意選擇），如果（U，V）∈E是穿過點集U和V-U的邊，即u∈U，v∈V- U，並且在所有這樣的邊中，
這個性質可以簡單地通過反證法來證明。假設G的任意最小生成樹T，對於點集U和V-U，（U，V）∈E是跨越這兩個點集的最小加權邊，並且T不包含最小加權邊
Prim算法在每壹步選擇連接U和V-U的權重最小的邊加入生成樹。
#包含& amplt；iostream & ampgt；
#包含& amplt；算法與數學。gt；
#define MAX_V 100
#定義INF 1000
使用命名空間std？
int main()
{
int V，E；
int i，j，m，n；
int cost【MAX _ V】【MAX _ V】；
int min cost【MAX _ V】；
bool使用了【MAX _ V】；
CIN & amp；gt；& ampgt；V & ampgt；& ampgt；e；
fill（min cost，mincost+V+1，INF）；
fill（used，used+V，false）；
for(I = 0；我& amplt；五；i++)
{
for(j = 0；強生公司。lt；五；j++)
{
if（I = = j）cost【I】【j】= 0；
else cost【I】【j】= INF；
}
}
for（m = 0；並購。lt；e；m++）
{
CIN & amp；gt；& ampgt；我& ampgt；& ampgt；強生公司。gt；& ampgt；成本【I】【j】；
成本【j】【I】=成本【I】【j】；
}
min cost【0】= 0；
int RES = 0；
while（真）
{
int v = V
for（m = 0；並購。lt；五；m++）
{
如果((！used【m】）& amp；amp& ampamp（最小成本【m】& amp；lt；mincost【v】）。
v = m；
}
if（V = = V）break；
used【v】= true；
RES+= mincost【v】；
for（m = 0；並購。lt；五；m++）
{
min cost【m】= min（min cost【m】，cost【v】【m】）；
}
}
cout & amplt；& amplt；資源和服務。lt；& amplt；endl
Kruskal算法在每壹步都直接將權重最小的無環邊添加到生成樹中，借助並集的數據結構我們可以完美實現。
貪婪算法的基礎知識就簡單介紹到這裏，希望能成為大家繼續深入學習的基礎。