算法中的贪心

贪心本质

一个贪心算法总是做出当前最好的选择&＃xff0c;

也就是说&＃xff0c;它期望通过局部最优选择&＃xff0c;从而得到

全局最优的解决方法

在贪心算法中&＃xff0c;我们应该注意以下几个问题&＃xff1a;

1 没有后悔药吃&＃xff0c;一旦做出选择&＃xff0c;不可以反悔

2有可能得到的不是最优解&＃xff0c;而是最优解的近似值

3选择什么样的贪心策略&＃xff0c;直接决定算法的好坏

贪心算法秘诀

知道了具有贪心选择和最优子结构性质就可以使用贪心算法&＃xff0c;秘诀&＃xff1a;

1 贪心策略

求解目标不同&＃xff0c;贪心策略也会不同

2 局部最优解

第一次先选一个最大的苹果&＃xff0c;第二次从剩下的苹果堆中选择一个最大的苹果放起来

3 全局最优

把所有的局部最优解合成为原来问题的一个最优解(a1,a2,a3,...)

物品可分割的装载问题我们称为背包问题&＃xff0c;物品不可分割的装载问题我们称为0-1背包问题

Dujkstra 算法是解决单源最短路径的贪心算法