贪心算法是一种在求解优化问题时常用的算法策略。
基本概念
贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，它不从整体最优上加以考虑，而是在每一步的决策中都采取当前状态下的最优决策。这种策略通常是局部最优解的选择，期望通过一系列的局部最优选择来达到全局最优解，但并不能保证一定能得到全局最优解。
工作流程
- 分解问题：将一个复杂的问题分解为一系列的子问题。例如，在找零问题中，把找零这个大问题分解为每次选择一种面额货币的子问题。
- 确定贪心策略：这是贪心算法的核心。比如在活动安排问题中，贪心策略是每次选择结束时间最早的活动，因为这样可以为后续活动留出更多的时间。在背包问题（部分背包问题）中，贪心策略是按照物品的价值与重量的比值（性价比）进行排序，优先选择性价比高的物品放入背包。
- 按策略求解：根据确定的贪心策略，一步一步地解决子问题。以活动安排为例，按照结束时间最早的活动优先安排，依次检查每个活动是否与已安排的活动冲突，不冲突就加入安排列表。
示例
- 找零问题
- 假设货币的面额有10元、5元、1元。要找零18元，贪心算法的做法是：首先选择一张10元，此时还剩下8元；接着选择一张5元，剩下3元；最后选择3张1元。通过每次选择面额最大的货币，快速地完成找零。
- 活动安排问题
- 假设有一系列活动，每个活动都有开始时间和结束时间。比如活动A（1,4），活动B（3,5），活动C（0,6），活动D（5,7），活动E（3,8）。按照贪心策略（选择结束时间最早的活动），首先选择活动A，因为它的结束时间最早是4。然后检查其他活动，发现活动B的开始时间3小于活动A的结束时间4，所以活动B不能选。接着看活动C，开始时间0小于4，不能选。活动D开始时间5大于4，可以选。活动E开始时间3小于4，不能选。所以最终选择的活动是A和D，这是一种比较合理的活动安排方式。
适用场景和局限性
- 适用场景：贪心算法适用于具有最优子结构性质的问题。即一个问题的最优解包含其子问题的最优解。例如，在部分背包问题中，整体的最优装载方案中，对于背包的任何剩余容量部分，装入的物品组合也是在该剩余容量下的最优选择。
- 局限性：由于贪心算法只是追求局部最优，对于一些复杂的问题，可能会陷入局部最优陷阱，无法得到真正的全局最优解。例如旅行商问题（TSP），如果使用贪心算法，每次选择距离当前城市最近的城市作为下一站，很可能得到的是一个比较差的旅行路线，而不是最短的全局路线。
贪心算法的应用案例:
- 任务调度问题
- 场景描述：假设有多个任务，每个任务都有一个完成时间和对应的收益。需要在有限的时间内安排任务，以获得最大的收益。
- 贪心策略：按照单位时间收益（收益/完成时间）对任务进行排序，优先选择单位时间收益高的任务。例如，有任务A（收益为10，完成时间为2），任务B（收益为15，完成时间为3），任务C（收益为8，完成时间为1）。计算单位时间收益，任务A为5，任务B为5，任务C为8。按照贪心策略，先选择任务C，再考虑任务A和B，这样可以在有限的时间内获得最大收益。
- 哈夫曼编码
- 场景描述：在数据压缩领域，需要将字符用二进制编码表示，使得总编码长度最短。
- 贪心策略：构造哈夫曼树。首先将所有字符出现的频率统计出来，把频率最低的两个节点合并为一个新节点，新节点的频率为这两个节点频率之和。不断重复这个过程&#
