信息学集训 | 14 贪心算法理论与实战

水亦心 AI与区块链技术

戳一戳!和我一起走进信息学的世界

导读

信息学能够有助于孩子未来工作发展,提升孩子的综合能力。


这一节课我们开始学习贪心算法,了解贪心算法的思想,并通过一些题目来熟练掌握贪心算法。

往期回顾

【NOIP竞赛/CSP认证】

▶  赛前必看!信息学名师带你复习NOIP竞赛初赛及CSP认证初赛


【信息学精华帖】

▶  收藏!交流会内容全公开,让你陪孩子更好地学习信息学

▶  信息学的万般好处!附C++必备基础知识总结

▶  信息学提高班知识体系详解与家长常见问题解答!让孩子赢在提高班学习的起跑线!

▶  再回首,最全提高班知识总结,做更优秀的自己!

▶  早知道!信息学集训班大揭秘!你想知道的的都在这!


信息学集训

▶  01 温故知新,以更好状态学习数据结构和算法
▶  02 信息学初赛必备计算机知识大串讲
▶  03 位运算与进制初步
▶  04 进制进阶与编码
▶  05 字符串进阶操作
▶  06 栈理论与实战
▶  07 队列理论与实战
▶  08 栈与队列实战
▶  09 算法及其复杂度
▶  10 经典排序算法思想精讲1
▶  11 经典排序算法思想精讲2

▶  12 排序算法分析与sort函数详解

▶  13 枚举算法理论与实战


【数据结构前导课】

▶  1 温故知新——一篇文章领略信息学C++知识结构
▶  2 披荆斩棘——只学C++,可以做哪些竞赛题
▶  3 运筹帷幄——一篇文章,让指针学起来也很简单!
▶  4 初试锋芒——顺序表写起来也很简单
▶  5 小试牛刀——STL库之vector数组
▶  6 触类旁通——链表基本理论与信息学竞赛必考点
▶  7 更进一步——STL库之List链表

▶  8 知“人”善任——深入理解顺序表和链表的区别与应用


【C++提高班教程】

▶  C++强化 | 01 新学期再出发!温故知新!
▶  C++强化 | 02 继续前行,三大结构终极介绍
▶  C++强化 | 03 一维数组入门
▶  C++强化 | 04 数组越界
▶  C++强化 | 05 一维数组经典应用
▶  C++强化 | 06 一篇文章带你掌握字符数组
▶  C++强化 | 07 二维数组
▶  C++强化 | 08 二维数组经典案例
▶  C++强化 | 09 一篇文章带你探索函数的奥秘
▶  C++强化 | 10 函数进阶必备
▶  C++强化 | 11 这样学递归,才不会觉得难
▶  C++强化 | 12 格式化输入输出与文件操作
▶  C++强化 | 13 结构体入门
  C++强化 | 14 结构体进阶


【C++基础班教程】

▶  C++总结 | 01 程序的世界
▶  C++总结 | 02 输出、换行与注释
▶  C++总结 | 03 变量定义、赋值与运算
▶  C++总结 | 04 算术运算符与赋值运算符
▶  C++总结 | 05 cin语句
▶  C++总结 | 06 程序中的数据类型
▶  C++总结 | 07 数据类型补充
▶  C++总结 | 08 顺序结构
▶  C++总结 | 09 if 和 if-else
▶  C++总结 | 10 if嵌套与逻辑运算符
▶  C++总结 | 11 开关语句switch-case
▶  C++总结 | 12 for循环及其应用
▶  C++总结 | 13 数据范围与数据类型
▶  C++总结 | 14 break与continue
▶  C++总结 | 15 while与do-while
▶  C++总结 | 16 循环嵌套及其应用

1 看个例子

首先我们先来看一个例子。


我们有如下几个数字:


12, 63, 56, 78, 9, 10, 15


我们从这几个数字中,选择4个,使得选出的数的和是最大的。应该怎么选呢?


选四个数,每次都要选择最大的,第一次我们选78,第二次63,第三次56, 第四次15。


在选择的时候,我们每次都很“贪心”,每次都选最大的。这个过程的思想,就是贪心算法。


贪心算法的意思就是说,每次,我们都要选择最好的。


2 贪心算法理论

让我们先来看一下贪心算法的理论吧

1 贪心介绍

首先我们来了解一下贪心算法。



1、贪心算法的定义


贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。


2、贪心算法的特点


贪心算法不从整体最优上加以考虑,只考虑当前的情况下最优解。算法得到的是在某种意义上的局部最优解。


此外贪心算法只是思想,即满足将情况分顺序,在每次操作能获取当前最优解(局部最优解),全局解为所有局部最优解的和。即可称之为贪心算法。


特别要说明:


1、有些情况下贪心算法也能得到全局最优解(比如我们的例子)。当我们能明确知道贪心算法就能取得最优解时,我们就可以选择贪心算法,因为贪心算法简单易用。


2、竞赛中,如果贪心算法不能保证所有数据得到最优解,但是能让其中某些数据得到最优解,而我们又难以找到更合适的算法时,可以使用贪心算法尽可能多的去获得分数。


2 贪心思路

贪心算法一般按如下步骤进行:


建立数学模型来描述问题;把求解的问题分成若干个子问题;对每个子问题求该问题下的最优解;将所有子问题的最优解合并。

3 贪心分析

首先我们来分析一下贪心算法。


1、贪心算法的优缺点


贪心算法的优点就是思路简单,使用较为容易。但是简单就导致其适用的场景一般比较少。其主要缺点如下:


1、不能保证算法是全局最优的。所以也很难适用于一些求最值或者求最优解的问题。

2、对于一些有上界约束性问题不适用,例如背包问题。


2、贪心算法的适用条件


利用贪心法求解的问题应满足如下两个条件


贪心选择性质最优子结构性质


对于贪心选择性质,即一个问题的整体最优解可通过一系列局部的最优解的选择达到,并且每次的选择可以依赖以前作出的选择,但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。


对于最优子结构性质,当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

3 贪心算法经典例题

接下来我们通过几道题目来看下贪心算法吧!

1 拿钱

一个钱包有100元,50元,20元,10元,5元,2元,1元各一张,只能拿五次,每次只能拿一张,问最多能拿多少钱?


这个题目非常简单,最简单的做法就是直接输出前五个的和:


#include<iostream>
using namespace std;

int main(){
  
  cout<<185<<endl;
  
  return 0;
}


开个玩笑开个玩笑,下面我们正式走进这道题目的题解。


首先说明一下,在竞赛中,这种做法是可以的,这种方法经常用来“骗分”。这道题目,思想是贪心的思想,我们一共拿五次,每次拿一张,想要总的最多,那每次就要拿最多的那个。


我们通过循环,每次判断求当前次的最大值,取到之后,就要把当前最大值加到总数上去,然后去掉最大值。


去掉最大值的方法有很多,例如我们直接将最大值设为0;或者每次将最大值放到最前面,下一轮遍历的时候,就从下一个位置开始判断,跳过当前轮的最大值;或者将数组最后一个位置数据存到最大值位置,然后数据长度-1;或者我们直接排序,计算前五个数的和。我们以第二种做法为例。


#include<iostream>
using namespace std;

int main(){
  //为了更好地凸显贪心思想,我们让数组无序
  int a[10] = {100, 5, 20, 1, 50, 10, 2};
  int sum = 0,t=0,l;
  for(int i = 0;i<5;i++){
    for(int j = i;j<7;j++){
      if(a[j]>t) {
        t = a[j];
        l = j;
      }
    }
    sum += t;
    a[l] = a[i];
    a[i] = t;
    t = 0;
  }
  cout<<sum<<endl;
  return 0;
}

2 拿宝藏

经验丰富的探险家到了沙漠,看到一片宝藏。他通过记录得知宝藏重量及其价值如下:


宝藏
A
B
C
D
E
重量
10
15
5
4
6
价值
500
600
500
120
900


现在他的背包能够装下重量为35的宝藏,每种宝藏可以只拿走其中一部分。问探险家最多能够拿走价值多少的宝藏?


这道题目我们想要价值最高,每次都拿价值最高的即可,剩下最后的可以拿一部分。我们要先计算重量为1时每种宝藏的价格。然后对此从大到小排序,然后拿够重量为35的宝藏即可。


代码如下:



#include<iostream>
#include<algorithm>
using namespace std;

struct BZ{
  int w,p,x;
}b[5];

bool cmp(BZ b1, BZ b2){
  return b1.x>b2.x;
}

int main(){
  int sum = 0,bg = 35;
  
  for(int i=0;i<5;i++){
    cin>>b[i].w>>b[i].p;
    b[i].x = b[i].w/b[i].p;
  }
  
  sort(b,b+5,cmp);
    
  for(int i = 0;i<5;i++){
    if(bg>=b[i].w){
      sum += b[i].p;
      bg -= b[i].w;
    }
    else{
      sum += b[i].x*bg;
      break;
    }
  }
  cout<<sum<<endl;
  return 0;
}


3 排队办理业务

组长带小组成员去办理业务,办理完的组员可以回去继续工作,组长预计每个成员办理业务花费的时间如下:


组员
A
B
C
D
E
办理时间
56
76
5
165
45


组长希望组员能够尽快回去工作,即在这里排队等待的时间最短。问最短时间是多少?


我们先不考虑时间最短,我们先考虑总的排队时间怎么计算。当第一个人办理业务的时候,后面4个人都要等待,一共需要等待4*t1,第二个人办理业务的时候,后面三个人都要等待,一共需要3*t2。全部的加起来就是4*t1 + 3*t2 + 2*t3 + t4。然后我们考虑怎么样等待时间最少,等待时间最少就是让和最小。和最小,那么t1到t4就要依次增大,所以我们安排贪心策略,就是让办理时间少的用户先办理,这样,总的等待的时间是最少的。


代码如下:


#include<iostream>
#include<algorithm>
using namespace std;

int main(){
  int a[5],sum = 0;
  
  for(int i=0;i<5;i++){
    cin>>a[i];
  }
  
  sort(a,a+5);
    
  for(int i = 0;i<4;i++){
    sum += a[i]*(4-i);
  }
  cout<<sum<<endl;
  return 0;
}


6 作业

本节课的作业,就是复习上面的所有知识,并完成下面的题目!

1 [NOIP2018 提高组 A] 铺设道路

春春是一名道路工程师,负责铺设一条长度为n的道路。整段道路可以看作是n块首尾相连的区域,一开始,第i块区域下陷的深度为  。


春春每天可以选择一段连续区间[L,R],填充这段区间中的每块区域,让其下陷深度减少1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为0。春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为0。


【输入说明】输入包含两行:第一行包含一个整数n,表示道路的长度。第二行包含n个整数,相邻两数间用一个空格隔开,第i个整数为di:【输出说明】输出文件仅包含一个整数,即最少需要多少天才能完成任务。
【输入示例】64 3 2 5 3 5【输出示例】9

AI与区块链技术

长按二维码关注

文章推荐