算法系列之贪心算法

在算法中，贪心算法（Greedy Algorithm）是一种常见的解决优化问题的算法。贪心算法的核心思想是：在每一步选择中都采取当前状态下最优的选择，即贪心的做出局部最优的决策，从而希望最终能够得到全局最优解。尽管贪心算法并不总是能够得到全局最优解，但在许多实际问题中，它能够提供足够好的解决方案，并且具有较高的计算效率。

本文将详细介绍贪心算法的基本概念、优缺点、实现步骤以及适用场景，并通过示例问题来展示贪心算法的应用。

基本概念

贪心算法它在每一步选择中都做出局部最优的选择，希望通过一系列局部最优的选择最终达到全局最优。贪心算法不会考虑过去的决策，而是一路向前的进行贪心的选择，不断缩小问题的范围，直至问题被解决。

我们通过找零问题来了解下贪心算法的工作原理：

问题描述：给定不同面额的硬币和一个总金额，要求用最少数量的硬币凑成该金额。

贪心策略：每次选择不大于且最接近剩余金额的最大的硬币，直到凑够总金额。

如图所示：我们需要找到凑够181元金额最少的硬币

优点及局限性

优点：

• 高效性：贪心算法通常具有较高的计算效率，适用于大规模问题。

• 简单性：贪心算法的实现通常较为简单，易于理解和编码。

缺点：

• 局部最优不一定全局最优：贪心算法并不总是能够得到全局最优解，有时只能得到近似解。

• 适用范围有限：贪心算法仅适用于具有贪心选择性质和最优子结构的问题。

示例：

比如币种有【1,20,50】，金额为60的话贪心算法只能找到 50+1*10 的兑换组合，有11张，而动态规划可以找到 20*3共3张的最优解。

贪心算法的实现步骤

贪心算法的实现通常包括以下几个步骤：

1. 问题建模：将问题抽象为一个优化问题，明确目标函数和约束条件。

2. 选择策略：确定每一步的局部最优选择策略。

3. 迭代求解：从初始状态开始，逐步应用选择策略，直到达到终止条件。

4. 验证解的有效性：验证最终得到的解是否满足问题的要求，并判断是否为全局最优解。

适用场景

1. 最优化问题

问题需要找到最大值或最小值。

• 找零问题（用最少数量的硬币找零）。
• 最小生成树问题（Prim算法、Kruskal算法）。
• 最短路径问题（Dijkstra算法）。

2. 区间问题

问题涉及区间选择或区间调度。

• 活动选择问题（选择最多的互不冲突的活动）。
• 区间覆盖问题（用最少的区间覆盖所有点）。

3. 分配问题

问题涉及资源的分配或任务的调度。

• 背包问题（分数背包问题，贪心算法可解）。
• 任务调度问题（最小化完成时间或最大化任务数量）。

4. 组合问题

问题涉及从一组元素中选择子集，满足某些条件。

• 霍夫曼编码（构建最优前缀编码）。
• 集合覆盖问题（近似解法）。

Java 实现示例

我们就用代码实现我们上边所示的找零问题,金额 161，面额【1,5,10,20,50,100】。代码如下：

/*** 贪心算法* 金额 161，面额[1,5,10,20,50,100],求最少的硬币个数*/
public class GreedyCoin {/*** 求解最少硬币个数* @param amount* @param coins* @return*/public static int minCoin(int amount, int[] coins) {//排序硬币面值Arrays.sort(coins);//初始化张数int count = 0;//循环面值,从大到小for (int i = coins.length - 1; i >= 0; i--) {count += amount / coins[i];amount = amount % coins[i];}// 如果金额没有完全凑齐，返回-1if(amount > 0){return -1;}return count;}public static void main(String[] args) {int amount = 161;int[] coins = {1,5,10,20,50,100};System.out.println(minCoin(amount, coins));}
}

示例题：观看⽂艺汇演

• 问题描述

某公园将举⾏多场⽂艺表演，很多演出都是同时进⾏，⼀个⼈只能同时观看⼀场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有 15 分钟的时间间隔，⼩明是⼀个狂热的⽂艺迷，想观看尽可能多的演出。现给出演出时间表，请帮⼩明计算他最多能观看⼏场演出。

• 输⼊

第⼀⾏为⼀个数 N ，表⽰演出场数， 1 <= N <= 1000 。
接下来 N ⾏，每⾏两个空格分割的整数，第⼀个整数 T 表⽰演出的开始时间，第⼆个整数 L 表⽰
演出的持续时间， T 和 L 的单位为分钟， 0 <= T <= 1440, 0 < L <= 100 。

• 输出

最多能观看的演出场数。

• 示例

示例1

输入

2
720 120
840 120

输出

1

示例2

输入

2
20 60
100 60

输出

2

示例3

输入

4
10 20
100 20
150 60
80 40

输出

3

• 问题分析

我们可以储存每⼀场演出的开始和结束时间，即按照 [start, end] 的⽅式进⾏储存。由于题⽬要求每间隔 15 分钟才能够看下⼀场演出，所以我们可以把每⼀场演出的结束时间再加上 15 分钟，这样题⽬就转变为：考虑所有不重叠的 [start, end] 区间的最⼤数⽬。

我们按开始时间对这些区间进行排序， 情况1：演出2的开始时间在演出1之后，就可以看完演出1再看演出2； 情况2：演出2的开始时间在演出1的期间，结束时间在演出1的结束时间之后，看完演出1无法看演出2 情况3：演出2的结束时间在演出1的结束时间之前，没必要看演出1。

• 代码实现

/*** 文艺演出类*/
public class Performance implements Comparable<Performance>{int start; // 演出开始时间int end;   // 演出结束时间public Performance(int start, int end) {this.start = start;this.end = end;}@Overridepublic int compareTo(Performance other) {return this.start - other.start; // 按开始时间从小到大排序}
}/*** 观看⽂艺汇演贪心算法
*/
public class GreedyPerformance {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();List<Performance> performances = new ArrayList<>();for (int i = 0; i < N; i++) {int start = scanner.nextInt();int during = scanner.nextInt();int end = start + during + 15;performances.add(new Performance(start, end));}Collections.sort(performances);int count = 0; // 观看演出的场数int lastEnd = 0; // 上一场演出的结束时间,初始化为0for(Performance performance:performances){int start = performance.start;int end = performance.end;// 如果当前演出的开始时间大于上一场演出的结束时间，则观看if(start >= lastEnd){count++;lastEnd=end;// 如果当前演出的开始时间小于上一场演出的结束时间，当前演出的结束时间大于上一场的结束时间，则不能观看}else if(start < lastEnd &&  lastEnd<= end){continue;// 如果当前演出的结束时间小于上一场的结束时间，则观看当前场}else if(lastEnd > end){lastEnd=end;}}System.out.println(count);}}

总结

贪心算法是一种简单而高效的优化策略，适用于许多实际问题。尽管它并不总是能够得到全局最优解，但在许多情况下，贪心算法能够提供足够好的解决方案，并且具有较高的计算效率。理解贪心算法的基本原理和适用场景，能够帮助我们在实际问题中更好地应用这一策略。