【算法笔记之算法思想】贪心算法
贪心算法
- 1.如何理解贪心算法?
-
- 1 举个例子
- 2 贪心算法解决问题的步骤
- 2.贪心算法实战分析
-
- 1.分糖果
- 2. 钱币找零
- 3. 区间覆盖(XXX)
- 4.总结
1.如何理解贪心算法? 1 举个例子 假设我们有一个可以容纳 100kg 物品的背包,可以装各种物品。我们有以下 5 种豆子,每种豆子的总量和总价值都各不相同。为了让背包中所装物品的总价值最大,我们如何选择在背包中装哪些豆子?每种豆子又该装多少呢?
文章图片
只要先算一算每个物品的单价,按照单价由高到低依次来装就好了。单价从高到低排列,依次是:黑豆、绿豆、红豆、青豆、黄豆,所以,我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。
2 贪心算法解决问题的步骤
- 第一步,当我们看到这类问题的时候,首先要联想到贪心算法:针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。
上面的例子中,限制值就是重量不能超过 100kg,期望值就是物品的总价值。这组数据就是 5 种豆子。我们从中选出一部分,满足重量不超过 100kg,并且总价值最大。
- 第二步,我们尝试看下这个问题是否可以用贪心算法解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。
类比到刚刚的例子,我们每次都从剩下的豆子里面,选择单价最高的,也就是重量相同的情况下,对价值贡献最大的豆子。
- 我们举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下,举几个例子验证一下就可以了。严格地证明贪心算法的正确性,是非常复杂的,需要涉及比较多的数学推理。而且,从实践的角度来说,大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明。
实际上,用贪心算法解决问题的思路,并不总能给出最优解。
如下图,从顶点S开始,找到一条到顶点T的最短路径—路径中的权值和最小;贪心算法解决的思路是:每次都选择一条跟当前顶点相连的权最小的边,直到找到顶点T,按这种思路,求出的最短路径是S->A ->E->T;路径长度是1+4+4=9;但是,这个路径并不是最短路径;下面的最短路径是 S->B->D->T ,这条路径的长度是 2+2+2=6;
贪心算法再这个问题上不工作的主要原因是,前面的选择会影响后面的选择;所以,即便我们第一步选择最优的走法(边最短),但有可能因为这一步选择,导致后面每一步的选择都很糟糕,最终也就无缘全局最优解了。
文章图片
2.贪心算法实战分析 1.分糖果 我们有 m 个糖果和 n 个孩子。我们现在要把糖果分给这些孩子吃,但是糖果少,孩子多(m
我的问题是,如何分配糖果,能尽可能满足最多数量的孩子?
把这个问题抽象成,从 n 个孩子中,抽取一部分孩子分配糖果,让满足的孩子的个数(期望值)是最大的。这个问题的限制值就是糖果个数 m。
这个问题如果通过贪心算法来解决呢?
对于一个孩子来说,如果小的糖果可以满足,我们就没必要用更大的糖果,这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面,对糖果大小需求小的孩子更容易被满足,所以,我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子,对我们期望值的贡献是一样的;2. 钱币找零 假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币,它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。我们现在要用这些钱来支付 K 元,最少要用多少张纸币呢?
我们每次从剩下的孩子中,找出对糖果大小需求最小的,然后发给他剩下的糖果中能满足他的最小的糖果,这样得到的分配方案,也就是满足的孩子个数最多的方案。
肯定是先用面值最大的来支付,如果不够,就继续用更小一点面值的,以此类推,最后剩下的用 1 元来补齐。
在贡献相同期望值(纸币数目)的情况下,我们希望多贡献点金额,这样就可以让纸币数更少,这就是一种贪心算法的解决思路。
3. 区间覆盖(XXX) 假设我们有 n 个区间,区间的起始端点和结束端点分别是 [l1, r1],[l2, r2],[l3, r3],……,[ln, rn]。我们从这 n 个区间中选出一部分区间,这部分区间满足两两不相交(端点相交的情况不算相交),最多能选出多少个区间呢?
文章图片
这个处理思想在很多贪心算法问题中都有用到,比如任务调度、教师排课等等问题。
问题的解决思路:
我们假设这 n 个区间中最左端点是 lmin,最右端点是 rmax。这个问题就相当于,我们选择几个不相交的区间,从左到右将 [lmin, rmax] 覆盖上。我们按照起始端点从小到大的顺序对这 n 个区间排序。
我们每次选择的时候,左端点跟前面的已经覆盖的区间不重合的,右端点又尽量小的,这样可以让剩下的未覆盖区间尽可能的大,就可以放置更多的区间。这实际上就是一种贪心的选择方法。
文章图片
public class Solution {/** 范围区间 */
private PriorityQueue> scopeList =
new PriorityQueue<>((o1, o2) -> compare(o1.getEnd(), o2.getEnd()));
/**
* 比较的算法
*
* @param val1
* @param val2
* @return
*/
public int compare(int val1, int val2) {
if (val1 > val2) {
return 1;
} else if (val1 < val2) {
return -1;
}
return 0;
}public void add(int start, int end) {
scopeList.offer(new ScopeBusi(start, end));
}/**
* 使用贪心算法,求最多能选出多少个区间呢?
*
* 算法实现,即按结束结点构建小顶堆,
*
* 然后在剩余的区间中查找,开始时间大小小顶堆的结束时间,这样即可求得最大不相交区间
*
* @return
*/
public List> countScope() {ScopeBusi scopeStartTmp = scopeList.poll();
List> result = new ArrayList<>();
result.add(scopeStartTmp);
while (!scopeList.isEmpty()) {ScopeBusi endBusi = scopeList.peek();
if (endBusi.getStart() >= scopeStartTmp.getEnd()) {
result.add(endBusi);
scopeStartTmp = endBusi;
scopeList.poll();
} else {
scopeList.poll();
}
}
return result;
}
}
4.总结 【【算法笔记之算法思想】贪心算法】贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法,这些算法都用到了贪心算法。 不要刻意去记忆贪心算法的原理,多练习才是最有效的学习方法。
贪心算法的最难的一块是如何将要解决的问题抽象成贪心算法模型,只要这一步搞定之后,贪心算法的编码一般都很简单。贪心算法解决问题的正确性虽然很多时候都看起来是显而易见的,但是要严谨地证明算法能够得到最优解,并不是件容易的事;
推荐阅读
- 大厂面试题|【2021Java后端面试题整理】JVM面试题+面经答案
- 论文学习笔记|论文学习笔记-t-SNE-1
- 学习笔记|R语言入门学习笔记1——5种数据模式(vector,matrix, factor, list, data frame)
- python寻峰算法_现代法谱估计(1)Yule Walker 方程法MATLAB及Python实现
- 论文笔记|【论文笔记】基于深度卷积神经网络的传感器融合实现自主驾驶
- 深度学习|Alex Net 论文学习笔记(含手撕代码)
- 算法|Pytorch框架训练MNIST数据集
- 云服务器修改dns服务器为阿里云公共dns服务器
- Kafka 索引文件
- 经典回溯算法(集合划分问题)