贪心算法地正确性的保证是，对于每一个独立的操作，满足按照给定的策略贪心，得到的结果都是正确的。
贪心算法的经典应用：
- Dijkstra 最短路；
- Kruskal 最小生成树；
- 哈夫曼编码。
经典的不能用贪心解决的问题：
- 背包问题；
- 二分图最大权匹配。
贪心的条件：拟阵。
- 什么是拟阵？
简而言之，就是一种“空间独立、线性无关”的结构，可以理解为一种所有局部最优解的集合。
- 对于一个拟阵 ，所以具有以下性质：
- 满足空集独立：即 ，即“空集线性独立”；
- 增广性（遗传性）：对于一个 ，满足如果 ，那么就有 ；
- 交换性：对于 ，，假设 ，则 ，。
用这个思路，只要解决生成树满足拟阵，就可以轻松的解决 kruskal 的证明。
