贪心算法是一种鼠目寸光的算法思路。算法的核心是，用局部最优解逼近全局最优解。是一种很简单粗暴的方式。
贪心算法，不是着眼于全局的解决方案。但是有些问题整体看上去简单，实现起来复杂度比较高，这时，我们采用贪心算法来逼近全局最优解。它是一种近似算法。(越是好的近似算法，越与最优解接近)
贪心算法对于背包问题，还行之有效吗？（如果不知道什么是背包问题，请百度）
在背包问题中，问题的衡量有两个参数，一个是重量，一个是价格。重量大的，未必价格贵。所以，用贪心策略并没有获得最优解，而得到一个近似解。假如背包问题中每个商品价格都是相同的，那么用贪心算法就可以把问题转化为重量最优解了。
背包问题对贪心算法的启示：
当整体最优解的获取方式，需要巨大成本时，选择一个成本较低的局部最优解才是性价比最高的解决方式。（贪心算法实现起来容易，成本较低，能快速解决问题，所以贪心算法有发挥的余地）
算法举例：（案例题目来自网络）
假设你办了个广播节目，要让全美个州的听众都收听得到，为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你试图在尽可能少的广播台播出。现有广播台名单如下：
算法举例
编码和结果
总结：
贪婪算法不是最优解，而是相对近似的结果。广度优先搜索和迪杰斯特拉都是贪心算法，但他们恰巧可以得到最优解。具体case具体分析。
网友评论