贪心算法
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，做出的是某种意义上的局部最优解。
思想
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每个子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解。
要素
- 贪心的选择
- 仅仅依据当前已有的信息做出选择，并且以后都不会改变这次选择。（区别与动态规划）
- 最优子结构
- 当一个问题的最优解包括其子问题的最优解时，称此问题具有最优子结构性质。
- 这个性质和动态规划的一样，最优子结构性质是可用动态规划算法或贪心算法求解的关键特征。
典型应用
- 背包问题
- Huffman编码
- 单源最短路径
- prim算法
- kruskal算法
例题