貪婪算法(貪心算法)是指在對問題進行求解時，在每一步選擇中都采取最好或者最優(即最有 利)的選擇，進而希望能夠導緻結果是最好或者最優的算法。
下面案例，假設有如下課程，希望盡可能多的将課程安排在一間教室裡：
| 課程 | 開始時間 | 結束時間 |
| 美術 | 9:00 | 10:00 |
| 英語 | 9:30 | 10:30 |
| 數學 | 11:00 | |
| 計算機 | 11:30 | |
| 音樂 | 12:00 |
這個問題看似要思考很多，實際上算法很簡單:
1. 選擇結束最早的課，便是要在這教室上課的第一節課
2. 接下來，選擇第一堂課結束後才開始的課，并且結束最早的課，這将是第二節在教室上的 課。
重複這樣做就能找出答案，這邊的選擇政策便是結束最早且和上一節課不沖突的課進行排序， 因為每次都選擇結束最早的，是以留給後面的時間也就越多，自然就能排下越多的課了。
每一節課的選擇都是政策内的局部最優解(留給後面的時間最多)，是以最終的結果也是近似最 優解(這個案例上就是最優解)。
貪婪算法所得到的結果往往不是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最 優解的結果。
貪婪算法并沒有固定的算法解決架構，算法的關鍵是貪婪政策的選擇，根據不同的問題選擇 不同的政策。
基本思路 其基本的解題思路為：
- 建立數學模型來描述問題
- 把求解的問題分成若幹個子問題
- 對每一子問題求解，得到子問題的局部最優解
- 把子問題對應的局部最優解合成原來整個問題的一個近似最優解
錢币找零問題：
假設1元、2元、5元、10元、20元、50元、100元的紙币分别有c0，c1，c2，c3，c4，c5，c6 張。現在要用這些錢來支付K元。至少要用多少張紙币？
解題思路：
用貪心算法的思想，很顯然，每一步盡可能用面值大的紙币即可。在日常生活中我們自然而然也是這麼做的。在程式中已經事先将Value按照從大到小的順序排好。
代碼如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define N 7
5
6 //int value[N]={1, 2, 5, 10, 20, 50, 100}; //800
7 //int count[N]={10, 2, 3, 1 ,2 ,3 , 5};
8 int value[N]={1, 2, 5, 10, 20, 50, 100}; //800
9 int count[N]={0, 0, 0, 0 ,3 ,1 , 0};
10
11 /**************************
12 *對輸入的零錢數，找到至少要用的紙币的數量
13 *參數：
14 * money - 要找/支付的零錢數
15 *傳回：
16 * 至少要用的紙币的數量，-1 表示找不開
17 *************************/
18
19 int solve(int money)
20 {
21 int num = 0;
22 int i = 0;
23 for(i=N-1; i>=0; i--)
24 {
25 int j = money/value[i]; //120 100 1 220 100 2
26 int c = j>count[i]?count[i]:j;
27 printf("需要用面值 %d 的紙币 %d 張\n", value[i], c);
28 money -= c*value[i];
29 num += c;
30 if(money==0) break;
31 }
32 if(money > 0) num = -1;
33 return num;
34 }
35
36 int main(void)
37 {
38 int money = 0;
39 int num = 0;
40 printf("請輸入要支付的零的數目：\n");
41 scanf_s("%d", &money);
42 num = solve(money);
43
44 if(num==-1)
45 {
46 printf("對不起，找不開\n");
47 }
48 else
49 {
50 printf("成功的使用至少%d 張紙币實作找零/支付！\n", num);
51 }
52
53 system("pause");
54 return 0;
55 }