贪心算法实例详解

1.简介

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

2.思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件，直到把所有数据枚举完。

贪心算法的思想如下：

a)建立数学模型来描述问题；

b)把求解的问题分成若干个子问题；

c)对每一子问题求解，得到子问题的局部最优解；

d)把子问题的解局部最优解合成原来解问题的一个解。

与动态规划不同的是，贪心算法得到的是一个局部最优解（即有可能不是最理想的），而动态规划算法得到的是一个全局最优解（即必须是整体而言最理想的），一个有趣的事情是，动态规划中的01背包问题就是一个典型的贪心算法问题。

3.学习方法

由浅入深，不妨先将动态规划中的01背包问题弄熟悉，再来学习贪心算法的基础思维，其实在很多时候自己并未发觉自己已经是在使用贪心了，当你基本掌握了一些贪心的概念的时候，可以做一些诸如装箱问题，切割问题，区域分配问题的题目，巩固自己的知识。

4.相关例题

有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法，最小生成树算法和最短路径算法，甚至是一些暴力求解题目，都是使用了贪心的这种思维。

可以直接从dotcpp网站标签中搜索贪心即可，贪心算法在很多题目中均或多或少有一些思维的应用，因此题目涵盖非常广阔，非常适合逐步练习。