常用贪心算法

贪心算法是一种思想简单、实现方便的算法，它在面对一些特殊问题时具有良好的效果。贪心算法的思想是：通过在每一步选择最优的方案来达到最终的全局最优。所以，贪心算法是一种应用最为广泛的算法之一，也是面试中常考的题型之一。

以下是几种常用的贪心算法：

1. 区间选点问题

区间选点问题是指：给定n个区间，从中选取k个区间并在这些区间的交集中标记上点，使得每个区间都至少有一个点被标记。首先需要将所有区间按照右端点从小到大排序，然后依次遍历每个区间，如果它没有被标记，那么就在它的右端点处标记上一个点。这样贪心算法就能得到最优解。

2. 活动选择问题

活动选择问题是指：在一些活动中选取一部分活动进行安排，而这些活动必须互不干扰，即它们没有时间上的重叠部分。该问题的解法是首先将所有活动按照结束时间从小到大排序，然后选择最早结束的活动，并将它加入到输出集合中。接下来依次选择结束时间不重复的活动，直到所有活动都被选完毕。

3. 零钱兑换问题

零钱兑换问题是指：给定一定面值的硬币集合和需要兑换的钱数，问最少需要多少硬币才能兑换成功。贪心算法在该问题中的实现方式是：从面值最大的硬币开始选取，如果选取当前面值的硬币可以使得总金额不超过目标金额，那么就选取该硬币；如果不能，就选取面值稍小一些的硬币，直到最终兑换成功。

4. 分数背包问题

分数背包问题是指：在有限容量的背包中，将各种物品按照一定比例加入到背包中，使得背包中放置的物品总价值最大。该问题的算法实现方式是：将所有物品按照单位重量的价值从大到小排序，然后依次选择单位价值最大的物品加入到背包中。

5. 贪心活动安排问题

贪心活动安排问题是指：在一组活动中选取尽可能多的活动进行安排，并且这些活动之间不产生冲突。该问题的算法实现方式是：将所有活动按照结束时间从早到晚排序，选取第一个活动并将其加入到安排集合中，然后从剩余的活动中依次选择结束时间早于已选中的最后一个活动的活动进行安排，直至所有活动都被选完。

以上是几种常用的贪心算法，虽然贪心算法思想简单，但是该算法在某些场景下仍然会出现不可避免的缺陷。因此，在使用贪心算法的过程中，需要对问题进行深入的分析，避免因为贪心思想的盲目使用导致算法的不完善。