⑴ 貪心演算法 活動安排問題
這道題的貪心演算法比較容易理解，我就不多說明了，只是提到一下演算法思路1、建立數學模型描述問題。我在這里將時間理解成一條直線，上面有若干個點，可能是某些活動的起始時間點，或終止時間點。在具體一下，如果編程來實現的話，將時間抽象成鏈表數組，數組下標代表其實時間，該下標對應的鏈表代表在這個時間起始的活動都有哪些，具體參照程序注釋。2、問題分解。為了安排更多的活動，那麼每次選取佔用時間最少的活動就好。那麼從一開始就選取結束時間最早的，然後尋找在這個時間點上起始的活動，以此類推就可以找出貪心解。程序代碼：#include<stdio.h>
struct inode //自定義的結構體
{
int end; //表示結束時間
inode *next; //指向下一個節點的指針
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num負責計數，i控制循環，a，b輸入時候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //輸入並建立數據結構
{
if(a==0&&b==0) break;
pt=new inode; //創建新的節點，然後將該節點插入相應的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //進行貪心演算法，i表示當前時間
{
if(start[i].next==NULL)
{
i++; //該時間無活動開始
}
else
{
int temp=10001; //臨時變數，存儲該鏈表中最早的終止時間
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //將當前時間設置成前一子問題的終止時間
num++;
}
}
printf("%d\n",num); //列印結果
return 0;
}代碼並不一定是最快速的，但是可以求出貪心解，如果你做的是ACM編程題目，不保證能AC注釋我盡力寫了，希望對你有幫助。
⑵ 數據結構之貪心演算法
貪婪演算法（Greedy）的定義：是一種在每一步選中都採取在當前狀態下最好或最優的選擇，從而希望導致結果是全局最好或最優的演算法。
貪婪演算法：當下做局部最優判斷，不能回退
（能回退的是回溯，最優+回退是動態規劃）
由於貪心演算法的高效性以及所求得答案比較接近最優結果，貪心演算法可以作為輔助演算法或解決一些要求
結果不特別精確的問題
注意：當下是最優的，並不一定全局是最優的。舉例如下：
有硬幣分值為10、9、4若干枚，問如果組成分值18，最少需要多少枚硬幣？
採用貪心演算法，選擇當下硬幣分值最大的：10
18-10=8
8/4=2
即：1個10、2個4，共需要3枚硬幣
實際上我們知道，選擇分值為9的硬幣，2枚就夠了
18/9=2
如果改成：
背包問題是演算法的經典問題，分為部分背包和0-1背包，主要區別如下：
部分背包：某件物品是一堆，可以帶走其一部分
0-1背包：對於某件物品，要麼被帶走（選擇了它），要麼不被帶走（沒有選擇它），不存在只帶走一部分的情況。
部分背包問題可以用貪心演算法求解，且能夠得到最優解。
假設一共有N件物品，第 i 件物品的價值為 Vi ，重量為Wi，一個小偷有一個最多隻能裝下重量為W的背包，他希望帶走的物品越有價值越好，可以帶走某件物品的一部分，請問：他應該選擇哪些物品？
假設背包可容納50Kg的重量，物品信息如下表：
將物品按單位重量 所具有的價值排序。總是優先選擇單位重量下價值最大的物品
按照我們的貪心策略，單位重量的價值排序： 物品A > 物品B > 物品C
因此，我們盡可能地多拿物品A，直到將物品1拿完之後，才去拿物品B，然後是物品C 可以只拿一部分.....
在不考慮排序的前提下，貪心演算法只需要一次循環，所以時間復雜度是O(n)
優點：性能高，能用貪心演算法解決的往往是最優解
缺點：在實際情況下能用的不多，用貪心演算法解的往往不是最好的
針對一組數據，我們定義了限制值和期望值，希望從中選出幾個數據，在滿足限制值的情況下，期望值最大。
每次選擇當前情況下，在對限制值同等貢獻量的情況下，對期望值貢獻最大的數據（局部最優而全局最優）
大部分能用貪心演算法解決的問題，貪心演算法的正確性都是顯而易見的，也不需要嚴格的數學推導證明
在實際情況下，用貪心演算法解決問題的思路，並不總能給出最優解
⑶ 貪心思想
在學習數據結構的時候，我們已經見過了貪心思想在Prim和Kruskal中的完美應用，貪心思想因為其的簡潔在演算法中經常會被用到，有的時候在生活中，我們也會無意中使用到l貪心演算法。比如在去shopping時，經常需要進行找零錢的過程，我們總是不自覺的先把大的找出來。
那麼什麼是貪心思想？
貪心演算法總是作出在當前看來最好的選擇，也就是說貪心演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。
只有在滿足最優子結構的情況下貪心演算法得到的結果才是最優結果。
比如找錢的問題，我要給你一百，那麼我盡可能每一次給你最多的。
或者比如磁碟的最優存儲問題，所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。
Prim和kruskal演算法都是每次選擇最小的邊納入生成樹。
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這也是貪心問題和動態規劃問題的主要區別。
在n行m列的正整數矩陣中，要求從每一行中選一個數，使得選出的n個數的和最大。
可運用貪心策略，選n次，每一次選相應行中的最大值即可。
但是，在一個n*m的方格陣中，每一格子賦予一個數，規定每次移動時只能向上或向右，現試找出一條路徑，使其從左下角至右上角所經過的權值之和最大。
同樣考慮貪心策略，從左下角向右上角移動，每次移動選擇權值較大的一個方向。
以2*3矩陣為例，採用貪心的策略得到的是1,3,4,6和為14但是實際的最優結果為1,2,100,6和為109.
所以說貪心演算法並不是總是可行，證明當前問題存在貪心選擇性質（全局最優解可以通過局部最優貪心選擇達到）和最優子結構性質（問題的最優解包含了其子問題的最優解）。所以貪心問題如果當前的選擇不會干擾之後的選擇，則不會出現問題。
其他的情況就需要進行證明，證明的最好辦法就是將最小子問題進行一步步的合並，直到最後還原為最後的原問題，若所得到的解是總體最優的則可以使用貪心思想，否則不可以。
比如上面的問題，我們的走一步的最優解為1，3，然後我們判斷一次走兩步的最優解是否任然為1,3這個路徑，答案顯然不是，變為 1,2,100這個路徑，所以顯然不能使用貪心思想。
假設1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現在要用這些錢來支付K元，至少要用多少張紙幣？用貪心演算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。
有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。
部分背包問題， 有n個物體，第i個物體重量為wi,價值為vi,在總重量不超過C的情況下，讓總價值盡可能的高。每個物體都可以只取一部分。
我們可以考慮重量和價值的比值作為單價。