贪心算法学习心得_贪心算法解决问题的心得

作者：天景科技苑 | 2024-08-05 21:19:40

踩

贪心算法解决问题的心得

这一周我在LeetCode上做了很多贪心算法的题。简单总结了个人理解贪心算法的核心思想

局部最优 :不从整体上进行考虑，对于一个问题总是做出当前情况的最优解。

这个核心思想使得贪心算法适用于无后效性的问题。因为一般贪心算法的思路就是建立问题的数学模型，然后将问题进行拆分，去求子问题的最优解，最后将子问题的最优解合成问题的解。

贪心算法的优点在于做决策只要考虑当前情况，条件较为简单，问题的复杂度大大降低。但其缺点就是局部的最优解不一定是全局的最优解。

简单的例子就是背包问题：两种情况

（1）0-1背包问题，物品不可分割。这时候使用贪心算法，很有可能导致浪费大量背包空间，局部的最优解往往不等于全局最优解。这类问题需要使用动态规划求解。

（2）背包问题，物品可以分割。这类问题就可以使用贪心算法，由局部最优解得到全局最优解。

总结：对于无后效性，有最优局部解的问题，使用贪心算法能够大大的降低问题复杂度，解决起来非常方便快捷。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/934317