Skip to content

贪心算法

什么时候能够使用贪心,现在最基本的想法就是遇到换零钱这类的问题不能使用贪心。

贪心的时候需要思考什么?首先,每次贪心的选择确定之后,后面不能再更改这个选择,比如说我已经将元素安排在了这个位置,后续不能再进行改动,如果还需要进行改定,就需要思考贪心的策略是不是不行了。 其次贪心的时候需要思考,每次的局部的最优选择是不是全局最优的选择,这是贪心的核心思想。排序往往能帮助到贪心。

贪心还有个重要过程就是举反例,在想到贪心的方案之后,应该尝试着先举反例看看,因为有的时候一下子看不出来题目是不是能用贪心,所以试着反例一下,如果没那么简单举出反例,使用贪心的信心应该能大幅增加。