【25届秋招备战C++】算法篇-贪心算法(Greedy)

一、简介

一种在每次决策时，总是采取在当前状态下的最好选择，从而希望导致结果是最好或最优的算法。通常用于解决一些最优化问题，如找零问题、霍夫曼编码、最小生成树问题等。在每一步都做出当前看起来最好的选择，不考虑这个选择对后续步骤的影响。这种策略有时能够导致全局最优解，但并不是所有问题都适用。在某些问题中，贪心算法可能只能得到局部最优解，而不是全局最优解。
如何验证可不可以用贪心算法呢？
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

二、解题思路

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

三、应用场景

• 分糖果问题：
  场景描述：有m个糖果要分给n个孩子，每个糖果的大小不同，每个孩子对糖果的需求也不同。目标是尽可能满足最多数量孩子的需求。
  解决方法：给所有孩子的需求排个序，从需求最小的孩子开始，用刚好能满足他的糖果来分给他，以此来分完所有的糖果。
• 找零钱问题：
  场景描述：有不同面额的纸币，需要找零K元，目标是使用最少的纸币数量。
  解决方法：先用面值最大的纸币去付钱，当再加一张就会超过K时，就更换小面额的，直至正好为K元。
• 区间覆盖问题：
  场景描述：给定n个区间，需要从中选出尽可能多的不相交的区间。
  解决方法：每次选择左端点大于等于已覆盖区间右边端点的区间，且该区间右端点尽可能小的，以保证未覆盖区间尽可能大，从而可以塞进去尽可能多的区间。
• 图的最小生成树：
  场景描述：在一个加权无向图中，需要找到一个包含所有顶点的无环子图，使得子图的总权重最小。
  解决方法：使用贪心策略，如Kruskal算法或Prim算法，逐步构建最小生成树。
• 哈夫曼编码：
  场景描述：需要为一组字符创建一个变长编码，使得编码后的字符串长度尽可能短。
  解决方法：构建一棵哈夫曼树，根据字符出现的概率分配编码。
• 活动安排问题：
  场景描述：有一系列活动，每个活动有开始时间和结束时间，目标是选择最大的互不冲突的活动集合。
  解决方法：按照结束时间对活动进行排序，然后贪心地选择结束时间最早的活动，并排除与其冲突的活动。

四、模板函数

没得模板，很难确定

五、参考

代码随想录
贪心算法-爱学习的饲养员
算法通关手册