贪心的人要会贪心算法
共 5633字,需浏览 12分钟
·
2021-07-30 21:32
前言
今天学习一下贪心算法,从字面意思大概能体会到,这个算法的大致意思。
"贪心" 这个词大家都懂,就是总想要最好的,说明这个人比较贪嘛。贪心算法也属于五大常用算法之一。
基本概念
贪心算法是指,在对问题求解时,总是做出在当前看来,是最好的选择。也就是说,不从整体最优上加以考虑,它所做出的仅仅是在,某种意义上的局部最优解。
贪心算法注重,贪心策略的选择。必须注意的是,贪心算法不是对所有问题,都能得到整体最优解,选择的贪心策略必须具备无后效性。
即某个状态以后的过程不会影响以前的状态,只与当前状态有关。所以,对所采用的贪心策略一定要仔细分析其是否满足无后效性。
解题思路
下面看一下,使用贪心算法,解决问题的几个例子。
跳跃游戏
题目:
定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表,你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
输入: [2, 3, 1, 1, 4]
输出:true
解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步,到达最后一个位置。
思路:贪心算法,每次找到可跳范围内的,数组值的最大值,看通过这个最大值,能否跳到尾部。不能跳到尾部,则遍历下一个,然后重复上述操作。
bool canJump(vector<int>& nums) {
int n = nums.size();
//最远可以到达的地方
int rightmost = 0;
//遍历数组
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
//如果较大值可以到达,则说明可以到达
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
会场安排问题
题目:
会场用来安排活动,每个活动,有一个开始时间和一个结束时间。在某个活动的开始时间,到结束时间这段范围内,其他活动不能再被安排,求最多能安排多少场活动。
#include<stdio.h>
#include<stdlib.h>
void GreedySelector(int n,int s[],int f[],int A[]){
int i, j;
//第一个活动要选,第一个结束时间最短,A[i]=1表示第i个活动入选
A[1] = 1;
//j=1表示取第一个活动的结束时间
j = 1;
//用i遍历每个活动
for(i = 2; i <= n; i++){
//这个活动的开始时间小于上个活动的结束时间
if(s[i] > f[j]){
A[i] = 1;
j = i;
} else {
A[i] = 0;
}
}
}
int main(){
int i;
//每个活动按活动的结束时间进行排序
//活动的开始时间
int s[] = {0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
//活动的结束时间
int f[] = {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int n=11, A[11];
GreedySelector(n, s, f, A);
for(i = 1; i <= n; i++){
if(A[i] == 1){
printf("%d\n", i);
}
}
return 0;
}
运行结果:1 4 8 11,这 4 个下标对应的活动。
策略选择:
开始时间最早优先(证明不可行)
占用时间少优先(证明不可行)
结束时间最早优先(使用贪心算法可以得到最优解)
加油站问题
题目:
一个汽车加满油后可以行使n千米,图中会经过一系列加油站,求到达最终加油的最少次数,给出每个加油站之间的距离。
#include<stdio.h>
//n表示汽车加满油后可以行使nkm
#define n 7
int main()
{
int a[n + 1] = {1, 2, 3, 4, 5, 1, 6, 6};
//k表示途中有k个加油站
int k = 7;
//油箱里的剩余油量,在起点时油量是满的
int rest = 7;
int count = 0;
int i = 0;
//n表示加满油可以行使n千米
while(i < n + 1){
//当前行程>rest
if(a[i] > rest){
//加油
count ++;
//重新赋值rest
rest = n;
}
rest -= a[i];
printf("rest=%d,i=%d\n", rest, i);
i ++;
}
printf("the mininum is %d.", count);
return 0;
}
每到一个加油站时,判断当前的油量,能否开到下一个加油站,再决定是否加油,i 表示对应的加油站。
贪心算法:局部最优能推导出整体最优,很容易,算法思维很常态化。
多次最优服务次序问题
问题描述:
设有n 个顾客同时等待一项服务。每个顾客需要服务一定时间。共有s 处可以
提供此项服务。
应如何安排n 个顾客的服务次序,才能使平均等待时间达到最小?平均等待时间是,n个顾客等待服务时间的总和除以n。
编程任务:
对于给定的,n个顾客需要的服务时间和s的值,编程计算最优服务次序。
#include<stdio.h>
#include<algorithm>
using namespace std;
//顾客数
#define n 10
//服务窗口数
#define s 2
int main()
{
//总共需要服务10位顾客,每位顾客需要服务的时间存在数组里
int a[n] = {56, 12, 1, 99, 1000, 234, 33, 55, 99, 812};
int i;
int sum = 0;
//服务窗口
int sub[s] = {0};
sort(a, a + n);
for(i = 0; i < n; i ++){
sub[i % s] += a[i];
sum += sub[i % s];
}
printf("%.2f", sum * 1.0 / n);
return 0;
}
运行打印:336.00
0 号窗口服务1,33,56....
1 号窗口服务12,55,99...
对应 0 号窗口,当服务 1 时,后面几位顾客需要等待的时间,就是前面几位顾客需要的服务时间的累加,前面有多少顾客就需要累加多少次。1 号窗口也是一样。
絮叨
贪心算法是一个很有趣的算法,场景适用于贪心算法,则解题非常容易。解题时需要明确,该题是否适用于贪心算法。
贪心算法在面试和工作也会有遇到的情况,希望大家结合本文弄懂此算法,后续相关算法知识,请见下期。
·················· END ··················
点击关注公众号,免费领学习资料
点“赞”和“在看”哦