贪心算法（greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。
1、从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停。
2、不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
总之：不求最优，仅仅求可行解。
1、把求解的问题分成若干个子问题；
2、对每一子问题求解，得到子问题的局部最优解；
3、把子问题的解局部最优解合成原来解问题的一个解。
给出一个正整数N，寻找最少的完全平方数，是他们的和为N:
直觉解法：12 = 4 + 4 + 4
贪心解法：12 = 9 + 1 + 1 + 1
假设给许多小朋友没人发一个饼干。每个小朋友都有一个“贪心指数”，成为 g(i), 即 g(i)表示这名小朋友需要的饼干大小的最小值。同时，每个饼干都有一个大小值 s(i)。如果 s(i) >= g(i),我们将饼干 j 分给小朋友i后，小朋友就会很开心。给定数组 s和g，问如何分配饼干，能让更多的小朋友开心:
private int findContentChild(Integer[] g, Integer[] s) {
Arrays.sort(g, cmp);
Arrays.sort(s, cmp);
int result = 0;
int si = 0;
int gi = 0;
while (gi < g.length && si < s.length) {
if (s[si] >= g[gi]) {
si++;
gi++;
result++;
} else {
gi++;
}
}
return result;
}
一个全局最优解可以通过局部最优得到。即当以贪心的方式解决一部分内容后，不会影响子问题的求解。
1、数学归纳法：类似于递推的过程，解决了规模为N的问题即可推导解决出规模为N+1的问题。(适用于有一个变量N在逐渐增加的情况)
2、反证法：假设他不正确，推导出矛盾。
有N头牛在畜栏中吃草。
每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。
给定N头牛和每头牛开始吃草的时间A以及结束吃草的时间B，每头牛在[A,B]这一时间段内都会一直吃草。
当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。
求需要的最小畜栏数目和每头牛对应的畜栏方案。
步骤1、将所有牛按开始吃草的时间排序；
步骤2、用队列维护当前所有畜栏的最后一头牛的吃草结束时间；
步骤3、如果当前的牛可以安排在堆顶的畜栏中，则将其安排进去，否则就新建一个畜栏；
证明：
反证法，假设存在一种方案，使得需要的畜栏数量更少，记其需要的畜栏数量是 m。
考虑在上述做法中，第一次新建第 m+1 个畜栏的时刻，不妨设当前处理的是第 i 头牛。
由于所有牛是按开始时间从小到大排好序的，所以现在前 m 个畜栏中最后一头牛的开始时间一定小于等于第 i 头牛的开始时间。
而且前 m 个畜栏中最小的结束时间大于等于第 i 头牛的开始时间，所以前 m 个畜栏里最后一头牛的吃草区间一定都包含第 i 头牛的开始时间，所以我们就找到了 m+1 个区间存在交集，所以至少需要 m+1 个畜栏，矛盾。
所以上述做法可以得到最优解，证毕。