贪心算法，又称“贪婪算法”。 在对问题求解时，老是做出在当前看来是最佳的选择。（局部最优解） 也就是说，不从总体最优上加以斟酌，他所做出的仅是在某种意义上的 局部最优解 。 贪心算法不是对所有问题都能得到总体最优解，但对规模至关广泛的许多问题他能发生总体最优解或者是总体最优解的 近似解 。（
注：贪心算法是一种高机能算法，繁杂度低，简单易用。 贪心算法求出来的结果不一定都是最优解。对于某些问题，它能求出最优解。而还有些问题，它能求出最优解的**“近似解”**。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
二、算法思想文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
“大事化小，小事化了”。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
- 大事化小：一个较大的问题，通过找到与子问题的堆叠，把繁杂的问题划分为多个小问题；
- 小事化了：从小问题找到决策的核心，肯定一种局部最优解的策略。
- 通过计算出局部的最优解，来推出全局的最优解或近似解。
伪代码如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
从问题的某一初始解动身
while
do
选择当前最优解作为可行解的一个解元素；
由所有解元素组合成问题的一个可行解。
复制代码
三、找零问题文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
这是一个求得 最优解 的贪心算法例子。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
场景：一位收银员，需要找零 88 元。 如何找零，所需要的纸/硬币的数量起码。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
思路：顺次找最大的纸币， 例如：找零88元， ¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
四、0-1背包问题文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
这是一个求得最优解的 近似解 的贪心算法例子。 而如果要想求得最优解，就要用到DP策略。而动态计划将在 下篇 介绍。文章源自微观生活（93wg.com）微观生活-https://93wg.com/5745.html
场景：一个小偷去商场偷东西，在背包称重有限下，怎么拿能使得取得收益越大？（每一件商品只有一个，只能选择拿与不拿）
- 贪心策略1：每一次取当前能拿得下的 最值钱 的商品。
- 贪心策略2：每一次取当前重量 最轻 的商品。
- 贪心策略3：每一次取 性价比最高 的商品。（即 价格/重量 的值最大的商品）
接下来咱们顺次分析，并且找出不是最优解的反例。
贪心策略1：选取价值最大的商品。
反例： 背包最大重量 W = 4kg
商品价格重量商品A3000元4kg商品B2000元3kg商品C1500元1kg
依据策略，首先选取商品A，接下来就没法再选取了，可是明明选取商品B、C更好。
贪心策略2：选取重量最轻的商品。
与策略1相似，举反例： 背包最大重量 W = 4kg
商品价格重量商品A3500元4kg商品B2000元3kg商品C1000元1kg
依据策略，首先选取商品C，接下来选取商品B，可是明明选取A更好。
以上就是微观生活（93wg.com）关于“算法小专栏：贪心算法”的详细内容，希望对大家有所帮助！
评论