算法系列之贪心算法
算法系列之贪心算法
在算法中，贪心算法（Greedy Algorithm）是一种常见的解决优化问题的算法。贪心算法的核心思想是：在每一步选择中都采取当前状态下最优的选择，即贪心的做出局部最优的决策，从而希望最终能够得到全局最优解。尽管贪心算法并不总是能够得到全局最优解，但在许多实际问题中，它能够提供足够好的解决方案，并且具有较高的计算效率。
本文将详细介绍贪心算法的基本概念、优缺点、实现步骤以及适用场景，并通过示例问题来展示贪心算法的应用。
基本概念
贪心算法它在每一步选择中都做出局部最优的选择，希望通过一系列局部最优的选择最终达到全局最优。贪心算法不会考虑过去的决策，而是一路向前的进行贪心的选择，不断缩小问题的范围，直至问题被解决。
我们通过找零问题来了解下贪心算法的工作原理：
问题描述：给定不同面额的硬币和一个总金额，要求用最少数量的硬币凑成该金额。
贪心策略：每次选择不大于且最接近剩余金额的最大的硬币，直到凑够总金额。
如图所示：我们需要找到凑够181元金额最少的硬币
优点及局限性
优点：
- 高效性：贪心算法通常具有较高的计算效率，适用于大规模问题。
- 简单性：贪心算法的实现通常较为简单，易于理解和编码。
缺点：
- 局部最优不一定全局最优：贪心算法并不总是能够得到全局最优解，有时只能得到近似解。
- 适用范围有限：贪心算法仅适用于具有贪心选择性质和最优子结构的问题。
示例：
比如币种有【1,20,50】，金额为60的话贪心算法只能找到
50+1*10
的兑换组合，有11张，而动态规划可以找到
20*3
共3张的最优解。
贪心算法的实现步骤
贪心算法的实现通常包括以下几个步骤：
- 问题建模：将问题抽象为一个优化问题，明确目标函数和约束条件。
- 选择策略：确定每一步的局部最优选择策略。
- 迭代求解：从初始状态开始，逐步应用选择策略，直到达到终止条件。
- 验证解的有效性：验证最终得到的解是否满足问题的要求，并判断是否为全局最优解。
适用场景
- 最优化问题
问题需要找到最大值或最小值。
- 找零问题（用最少数量的硬币找零）。
- 最小生成树问题（Prim算法、Kruskal算法）。
- 最短路径问题（Dijkstra算法）。
- 区间问题
问题涉及区间选择或区间调度。
- 活动选择问题（选择最多的互不冲突的活动）。
- 区间覆盖问题（用最少的区间覆盖所有点）。
- 分配问题
问题涉及资源的分配或任务的调度。
- 背包问题（分数背包问题，贪心算法可解）。
- 任务调度问题（最小化完成时间或最大化任务数量）。
- 组合问题
问题涉及从一组元素中选择子集，满足某些条件。
- 霍夫曼编码（构建最优前缀编码）。
- 集合覆盖问题（近似解法）。
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];
}
// 如果金额没有完全凑齐，返回-1
if(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;
}
@Override
public 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; // 上一场演出的结束时间,初始化为0
for(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);
}
}
总结
贪心算法是一种简单而高效的优化策略，适用于许多实际问题。尽管它并不总是能够得到全局最优解，但在许多情况下，贪心算法能够提供足够好的解决方案，并且具有较高的计算效率。理解贪心算法的基本原理和适用场景，能够帮助我们在实际问题中更好地应用这一策略。