贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件,直到把所有数据枚举完。
贪心算法的思想如下:
a)建立数学模型来描述问题;
b)把求解的问题分成若干个子问题;
c)对每一子问题求解,得到子问题的局部最优解;
d)把子问题的解局部最优解合成原来解问题的一个解。
与动态规划不同的是,贪心算法得到的是一个局部最优解(即有可能不是最理想的),而动态规划算法得到的是一个全局最优解(即必须是整体而言最理想的),一个有趣的事情是,动态规划中的01背包问题就是一个典型的贪心算法问题。
由浅入深,不妨先将动态规划中的01背包问题弄熟悉,再来学习贪心算法的基础思维,其实在很多时候自己并未发觉自己已经是在使用贪心了,当你基本掌握了一些贪心的概念的时候,可以做一些诸如装箱问题,切割问题,区域分配问题的题目,巩固自己的知识。
有很多经典的应用,比如霍夫曼编码(Huffman Coding)、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法,最小生成树算法和最短路径算法,甚至是一些暴力求解题目,都是使用了贪心的这种思维。
可以直接从dotcpp网站标签中搜索贪心即可,贪心算法在很多题目中均或多或少有一些思维的应用,因此题目涵盖非常广阔,非常适合逐步练习。
1197 | 发工资咯 |
1453 | 蓝桥杯历届试题-翻硬币 |
1462 | 蓝桥杯基础练习VIP-Huffuman树 |
知识点标签:贪心
本文固定URL:https://www.dotcpp.com/course/169
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程