##什么是算法>贪心算法
一种常见的解决优化类型的问题，基本的思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优解的决策，以期待获得全局最优解。
##算法>贪心算法与动态规划的区别（二者都为解决优化问题）
1.动态规划会根据当前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
##零钱对换问题引入算法>贪心算法
给定 𝑛 种硬币，第 𝑖 种硬币的面值为 𝑐𝑜𝑖𝑛𝑠[𝑖−1] ，目标金额为 𝑎𝑚𝑡 ，每种硬币可以重复选取，问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额，则返回 −1 。
给定目标金额，我们贪心地选择不大于且最接近它的硬币，不断循环该步骤，直至凑出目标金额为止。
##代码示例
//c++代码示例 int coinChangeGreedy(vector<int> &coins,int amt) {//假设coins列表有序int i = coins.size() - 1 ;int count = 0 ;while (amt > 0 ){while (i > 0 && coins[i] > amt){i-- ; }amt = amt - coins[i] ;count++ ; } return amt == 0 ? count : -1 ; }
##优点与局限性
算法>贪心算法虽然操作直接简单，而且效率也很高，但是有的时候并不能保证找到全局最优解，有可能是非常差的解。
##对应对换硬币这个例子，做以下分析
- 正例 𝑐𝑜𝑖𝑛𝑠=[1,5,10,20,50,100]：在该硬币组合下，给定任意 𝑎𝑚𝑡 ，算法>贪心算法都可以找到最优解。
- 反例 𝑐𝑜𝑖𝑛𝑠=[1,20,50]：假设 𝑎𝑚𝑡=60 ，算法>贪心算法只能找到 50+1×10 的兑换组合，共计 11 枚硬币，但动态规划可以找到最优解 20+20+20 ，仅需 3 枚硬币。
- 反例 𝑐𝑜𝑖𝑛𝑠=[1,49,50]：假设 𝑎𝑚𝑡=98 ，算法>贪心算法只能找到 50+1×48 的兑换组合，共计 49 枚硬币，但动态规划可以找到最优解 49+49 ，仅需 2 枚硬币。
##局限性
1.可以保证找到最优解：算法>贪心算法在这种情况往往是最优选择，因为它往往比回溯、动态规划更高效。
2.可以找到近似最优解：算法>贪心算法在这种情况也是可以采用的。对于很多复杂的问题，寻找全局最优解非常的困难，能比较高效率找到次优解也是很不错的选择。
##算法>贪心算法特性
##算法>贪心算法的解题步骤
##解题流程
- 问题分析：梳理与理解问题特性，包括状态定义、优化目标和约束条件等。
- 确定贪心策略：确定如何在每一步中做出贪心选择。这个策略能够在每一步减小问题的规模，并最终解决整个问题。
- 正确性证明：通常需要证明问题具有贪心选择性质和最优子结构。这个步骤可能需要用到数学证明，例如归纳法或反证法等。
确定贪心策略：
- 不同问题的贪心策略的差异较大。对于许多问题来说，贪心策略比较浅显，我们通过一些大概的思考与尝试就能得出。而对于一些复杂问题，贪心策略可能非常隐蔽，这种情况就非常考验个人的解题经验与算法能力了。
- 某些贪心策略具有较强的迷惑性。当我们满怀信心设计好贪心策略，写出解题代码并提交运行，很可能发现部分测试样例无法通过。这是因为设计的贪心策略只是“部分正确”的，上文介绍的零钱兑换就是一个典型案例。
##算法>贪心算法的典型例题
- 硬币找零问题：在某些硬币组合下，算法>贪心算法总是可以得到最优解。
- 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么算法>贪心算法就可以得到最优解。
- 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么算法>贪心算法在一些情况下可以得到最优解。
- 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
- 霍夫曼编码：霍夫曼编码是一种用于无损数据压缩的算法>贪心算法。通过构建霍夫曼树，每次选择出现频率最低的两个节点合并，最后得到的霍夫曼树的带权路径长度（编码长度）最小。
- Dijkstra 算法：它是一种解决给定源顶点到其余各顶点的最短路径问题的算法>贪心算法。
