一、简介
① 贪心算法的基本概念
贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在某种意义上的局部最优解,它是最自然智慧的算法。贪心算法用一种局部最功利的标准,总是能做出在当前看来是最好的选择,难点在于证明局部最优解最功利的标准可以得到全局最优解。贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。需要注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性(即某个状态以后的过程不会影响以前的状态,只与当前状态有关)。因此,对所采用的贪心策略一定要仔细分析其是否满足无后效性。② 贪心算法的算法解释
正例:通过一个例子来解释,假设一个数组中 N 个正数,第一个挑选出来的数乘以 1,第二个挑选出来的数乘以 2,同理,第 N 次挑选出来的数乘以 N,总的加起来是我们的分数,那么怎么挑选数字使我们达到最大分数?数组按从小到大的顺序排序,按顺序依次挑选,最终结果就是最大的。本质思想是因子随着挑选次数的增加会增大,尽量让大数去结合大的因子。③ 贪心算法的证明问题
如何证明贪心算法的有效性?一般来说,贪心算法不推荐证明,很多时候证明是非常复杂的。例如:给定一个由字符串组成的数组 strs,必须把所有的字符串拼接起来,返回所有可能的拼接结果中,字典序最小的结果。<如果觉得《【数据结构与算法】之深入解析“贪心算法“的原理解析和算法实现》对你有帮助,请点赞、收藏,并留下你的观点哦!