贪心的人要会贪心算法

moon聊技术

共 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 ··················

点击关注公众号,免费领学习资料

                                                                                    点“赞”和“在看”哦

浏览 19
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报