贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有 利)的选择，从而希望能够导致结果是最好或者最优的算法。
下面案例，假设有如下课程，希望尽可能多的将课程安排在一间教室里：
| 课程 | 开始时间 | 结束时间 |
| 美术 | 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 }