贪婪算法

算法简介

这种算法是为了解决一些无法完成的问题（例如使用常规算法计算会超时等），当然这种算法运算出来的并不一定是最优解，而是近似解。

常见的贪婪算法

1.广度优先搜索算法
2.狄克斯特拉算法

算法过程

只要每次都选择当前的最优解即可。
例如你有一个包只可以装35KG的东西，现在有A 15KG，B 20KG,C 30KG.所以按照贪婪算法（选择当前的最优解），你应该一开始就放入C30KG的东西，放入后你就无法放入另外的了，那么30KG就是贪婪算法的最终结果（近似解）。（虽然不是最优结果，但相比放入B20KG和A15KG来说，你不需要去寻找到这种组合，因此节省了时间）

为什么能够解决无法完成的问题

举一个例子
当你需要在全国的N个省里，找一些广播台来给你发广告，每个广播台只能发送广告到特定的省份。例如：

现在你的任务就是找出一个最少广播台数量的组合，这个组合必须包含所有的省份。
按照常规算法(n代表广播台的数量)
你把所有的广播台的组合都找出来（组合数量为：2^n）
在找出这些组合里哪些满足包含了所有的省份，并在这些满足了先前条件的组合里找出广播台最少的组合。
我们可以知道这个算法的时间复杂度为O(2^n)，假设每秒你可以计算10个子集，那么当有32个广播台的时候，计算完成需13年

那么使用贪婪算法呢？
你只要每次都选择能够拥有覆盖当前还未覆盖省份最多的广播台，直到所有的省份都覆盖。这样算法的时间复杂度就变成了O(n ^ 2)了，同样的当有32个广播台时你只需要102秒左右就能计算完成了。是不是炒鸡快呐！

具体算法

有时间在更新