贪心算法种类

贪心算法是一种常见的算法思想，它在解决一些最优化问题时非常有效。贪心算法按照优先级从高到低排序，以每个阶段的局部最优解为基础求得全局最优解。因为它的时间复杂度一般比较低，所以在一些追求效率的场合，贪心算法常常被使用。下面将从多个角度介绍贪心算法的种类。

1. 基本贪心算法

基本贪心算法就是将问题划分为阶段，每个阶段都取局部最优解，最后得到全局最优解。基本贪心算法有以下特点：

（1）每个阶段的局部最优解对于下一个阶段的决策没有任何影响；

（2）贪心算法需要证明每个阶段的局部最优解也是全局最优解；

（3）贪心算法要求问题具有最优子结构性质，即一个问题的最优解可以通过它的子问题的最优解来构造。

2. 分数背包问题

当物品可以分割成任意大小时，称为分数背包问题。在分数背包问题中，每个物品都有一个价值和一个重量，每个物品的单位价值是已知的，背包有一个容量限制。分数背包问题是一种基本的贪心算法问题。其思路是按照单位价值从大到小排序，每次选择当前单位价值最大的物品，并将物品分割成若干份，可以部分装入背包。

3. 区间调度问题

区间调度问题是贪心算法中的一个典型例子。该问题的目标是安排最多的互相兼容的任务，以使得时间利用效率最高。具体来说，我们需要安排一批任务，并且对于每个任务有一个起始时间和结束时间。我们需要在给定时间限制和资源限制的情况下尽可能多地完成任务。该问题的贪心策略是按照结束时间排序，并且每次选择结束时间最早的任务。

4. 钱币找零问题

钱币找零问题是计算机程序中的一个经典问题。在钱币找零问题中，我们需要找零给定数量的钱，找零的钱币包括 coins 中的硬币。找零问题是一种典型的贪心算法问题。找零问题可以使用贪心策略解决。我们需要按照面值从大到小排序，每次选择面值最大的硬币，从钱数中减去硬币面值，直到钱数等于 0。