贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法一般按如下步骤进行：
①建立数学模型来描述问题。
②把求解的问题分成若干个子问题。
③对每个子问题求解，得到子问题的局部最优解。
④把子问题的解局部最优解合成原来解问题的一个解。
例题1.分发饼干
解题思路
要尽可能满足越多数量的孩子，可以将孩子们的胃口值 g[i] 和 饼干的尺寸 s[j] 进行排序。这里是按照从大到小的顺序进行排序。
然后让尺寸最大的饼干 maxSizeCookies 去满足胃口值最大（最贪心）mostGreedy的孩子，如果能满足（让他满意），则留给下一个次贪心孩子的饼干也将是当前看来最大的饼干，用尺寸次大的饼干去满足他，依次类推；如果不能满足，那么胃口值最大（最贪心）的孩子，对不起，无法满足你的胃口让你开心，此时用尺寸最大的饼干 maxSizeCookies 去满足胃口值次大（次贪心）的孩子，尽量满足次贪心的孩子，依次类推。
举例
假设 g = [1,2], s = [1,2,3]。
1.将 g 和 s 从大到小排序，得到 g = [2,1], s = [3,2,1]；
2.用尺寸最大的饼干 s[0] = 3 去满足最贪心（胃口值最大）g[0] = 2 的孩子 ，能满足；
3.用尺寸次大的饼干 s[2] = 2 去满足次贪心（胃口值次大）g[0] = 1 的孩子 ，能满足；
满足孩子的最大数值为 2。
代码如下
int comp(const void *a, const void *b) {
return *(int *)b - *(int *)a;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
qsort(g, gSize, sizeof(int), comp);
qsort(s, sSize, sizeof(int), comp);
int res = 0;
int i = 0, j = 0;
while (i < gSize && j < sSize) {
if (s[j] >= g[i]) {
j++;
i++;
res++;
} else {
i++;
}
}
return res;
}
2.柠檬水找零
- 简单模拟，按贪心算法，优先找零大面额
- 每10元，需要找零1张5元
- 每20元，需要找零1张10元和1张5元，或者3张5元
代码如下
bool lemonadeChange(int* bills, int billsSize){
int fives = 0, tens = 0;
for (int i = 0; i < billsSize; i++) {
int bill = bills[i];
if (bill == 5) {
fives++;
}
else if (bill == 10) {
if (fives == 0) {
return false;
}
tens++;
fives--;
}
else {
if (fives >= 1 && tens >= 1) {
tens--;
fives--;
}
else if (fives >= 3) {
fives -= 3;
}
else {
return false;
}
}
}
return true;
}
3.加油站
能够走完的条件有两个
1.获得的汽油的量大于总油耗
2.车从i站能开到i+1
设 三个变量total、cur、ans
分别记记录 可获得的总油量-总油耗、当前油耗情况、出发位置
在遍历数组过程中当cur小于0时，表明从ans位置出发到i位置为
死路，无法通行，此时应将cur置零，ans改为i+1
如果最后total>= 0 即ans位置出发可以环行一周，则返回ans，
否则返回 -1.
代码如下
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
// total记录可获得的总油量-总油耗， cur记录当前油耗情况， ans记录出发位置
int total = 0, cur = 0, ans = 0;
for(int i=0;i
