如何用Python实现贪心算法？

本文共计1043个文字，预计阅读时间需要5分钟。

贪心算法是指，在求解问题时，总是做出当前情况下最好的选择，不全局最优考虑。换句话说，贪心算法不考虑整体最优，而是关注某种意义上的局部最优解。

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。

步骤

1. 遍历初始集合X中的备选元素
2. 利用贪心策略在X中确定一个元素，并将其加入到可行解S中
3. 得到可行解S

P即为贪心策略，用来选择符合条件的元素。

例子——硬币找零

假设某国硬币面值有1,5,10,25,100元五种面额，若店员为顾客找零时，需要给顾客找零a=36元，求硬币数最少的情况。