程序员算法基础——贪心算法

前言

贪心是人类自带的能力,贪心算法是在贪心决策上进行统筹规划的统称。

比如一道常见的算法笔试题----跳一跳:

  • 有n个盒子排成一行,每个盒子上面有一个数字a[i],表示最多能向右跳a[i]个盒子;
  • 小明站在左边第一个盒子,请问能否到达最右边的盒子?
  • 比如说:[1, 2, 3, 0, 4] 可以到达第5个盒子;
  • [3, 2, 1, 0, 4] 无法到达第5个盒子;

我们自然而然能产生一种解法:尽可能的往右跳,看最后是否能到达。

本文即是对这种贪心决策的介绍。

正文

贪心算法基础概念

狭义的贪心算法指的是解最优化问题的一种特殊方法,解决过程中总是做出当下最好的选择,因为具有最优子结构的特点,局部最优解可以得到全局最优解;这种贪心算法是动态规划的一种特例。能用贪心解决的问题,也可以用动态规划解决。

而广义的贪心指的是一种通用的贪心策略,基于当前局面而进行贪心决策。以跳一跳的题目为例:

  • 我们发现的题目的核心在于向右能到达的最远距离,我们用maxRight来表示;

此时有一种贪心的策略:从第1个盒子开始向右遍历,对于每个经过的盒子,不断更新maxRight的值。

贪心算法的思考过程

贪心的思考过程类似动态规划,依旧是两步:大事化小,小事化了。

大事化小:

一个较大的问题,通过找到与子问题的重叠,把复杂的问题划分为多个小问题;

小事化了:

从小问题找到决策的核心,确定一种得到最优解的策略,比如跳一跳中的向右能到达的最远距离;

在证明局部的最优解是否可以推出全局最优解的时候,常会用到数学的证明方式。

贪心算法的具体应用

1、纸币找零问题

有1元、2元、5元、10元的纸币分别有a[1], a[2], a[3], a[4]张,要用这些纸币凑出m元,至少要用多少张纸币?

如果是动态规划:

  • 要凑出m元,必须先凑出m-1、m-2、m-5、m-10元,我们用dp[i]表示凑出i元的最少纸币数;
  • 有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1;
  • 容易知道dp[1]=dp[2]=dp[5]=dp[10]=1;

根据以上递推方程和初始化信息,可以容易推出dp[1~m]的所有值。

似乎有些不对?平时我们找零钱有这么复杂吗?

从贪心算法角度出发,当m>10且我们有10元纸币,我们优先使用10元纸币,然后再是5元、2元、1元纸币。

  • 从日常生活的经验知道,这么做是正确的,但是为什么?
  • 假如我们把题目变成这样,原来的策略还能生效吗?
  • 有1元、5元、7元的纸币分别有a[1], a[2], a[3]张,要用这些纸币凑出m元,至少要用多少张纸币?

接下来我们来分析这种策略:

  • 已知对于m元纸币,1,2,5元纸币使用了a,b,c张,我们有a+2b+5c=m;

假设存在一种情况,1、2、5元纸币使用数是x,y,z张,使用了更少的5元纸币(z

我们令k=5*(c-z),k元纸币需要floor(k/2)张2元纸币,k%2张1元纸币;(因为如果有2张1元纸币,可以使用1张2元纸币来替代,故而1元纸币只能是0张或者1张)

容易知道,减少(c-z)张5元纸币,需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币,而这使得x+y+z必然大于a+b+c。

由此我们知道不可能存在使用更少5元纸币的更优解。

所以优先使用大额纸币是一种正确的贪心选择。

对于1、5、7元纸币,比如说要凑出10元,如果优先使用7元纸币,则张数是4;(1+1+1+7)

但如果只使用5元纸币,则张数是2;(5+5)

在这种情况下,优先使用大额纸币是不正确的贪心选择。(但用动态规划仍能得到最优解)

2、服务器任务安排问题

服务器有n个任务要执行,每个任务有开始时间Si秒和结束时间Ti秒,同一时间只能执行一个任务。

问如何安排任务,使得在时间m内尽可能多的完成任务。

如果是动态规划:

前i秒的完成的任务数,可以由前面1~i-1秒的任务完成数推过来。

  • 我们用dp[i]表示前i秒能完成的任务数;

在计算前i秒能完成的任务数时,对于第j个任务,我们有两种决策:

  1. 不执行这个任务,那么dp[i]没有变化;
  2. 执行这个任务,那么必须腾出来(Sj, Tj)这段时间,那么dp[i] = max(dp[i], dp[ S[j] ] ) + 1;

比如说对于任务j如果是第5秒开始第10秒结束,如果i>=10,那么有dp[i]=max(dp[i], dp[5] + 1);(相当于把第5秒到第i秒的时间分配给任务j)

再考虑贪心的策略,现实生活中人们是如何安排这种多任务的事情?我换一种描述方式:

  • 小明在学校兼职,小明一天兼职的时间有10个小时;
  • 现在有多个兼职岗位,每个岗位有个开始时间和结束时间,小明同一时间只能做一个兼职;

问小明每天最多能做几份兼职?

我们自然而然会想到一个策略:先把结束时间早的兼职给做了!

为什么?

因为先做完这个结束时间早的,能留出更多的时间做其他兼职。

我们天生具备了这种优化决策的能力。

3、分糖果问题

n个小朋友玩完游戏后,老师准备给他们发糖果;

每个人有一个分数a[i],如果比左右的人分数高,那么糖果也要比左右的多,并且每个小朋友至少有一颗。

问老师最少准备多少糖果。

这是一道LeetCode题目。

这个题目不能直接用动态规划去解,比如用dp[i]表示前i个人需要的最少糖果数。

因为(前i个人的最少糖果数)这种状态表示会收到第i+1个人的影响,如果a[i]>a[i+1],那么第i个人应该比第i+1个人多。

即是这种状态表示不具备无后效性。

如果是我们分配糖果,我们应该怎么分配?

答案是:从分数最低的开始。

按照分数排序,从最低开始分,每次判断是否比左右的分数高。

假设每个人分c[i]个糖果,那么对于第i个人有c[i]=max(c[i-1],c[c+1])+1; (c[i]默认为0,如果在计算i的时候,c[i-1]为0,表示i-1的分数比i高)

但是,这样解决的时间复杂度为O(NLogN),主要瓶颈是在排序。

如果提交,会得到Time Limit Exceeded的提示。

我们需要对贪心的策略进行优化:

  • 我们把左右两种情况分开看。

如果只考虑比左边的人分数高时,容易得到策略:

  • 从左到右遍历,如果a[i]>a[i-1],则有c[i]=c[i-1]+1;否则c[i]=1。

再考虑比右边的人分数高时,此时我们要从数组的最右边,向左开始遍历:

  • 如果a[i]>a[i+1], 则有c[i]=c[i+1]+1;否则c[i]不变;

这样讲过两次遍历,我们可以得到一个分配方案,并且时间复杂度是O(N)。

4、小船过河问题

n个人要过河,但是只有一艘船;船每次只能做两个人,每个人有一个单独坐船的过河时间a[i],如果两个人(x和y)一起坐船,那过河时间为a[x]和a[y]的较大值。

问最短需要多少时间,才能把所有人送过河。

题目给出关键信息:1、两个人过河,耗时为较长的时间;

还有隐藏的信息:2、两个人过河后,需要有一个人把船开回去;

要保证总时间尽可能小,这里有两个关键原则:应该使得两个人时间差尽可能小(减少浪费),同时船回去的时间也尽可能小(减少等待)。

先不考虑空船回来的情况,如果有无限多的船,那么应该怎么分配?

答案:每次从剩下的人选择耗时最长的人,再选择与他耗时最接近的人。

再考虑只有一条船的情况,假设有A/B/C三个人,并且耗时A

那么最快的方案是:A+B去, A回;A+C去;总耗时是A+B+C。(因为A是最快的,让其他人来回时间只会更长,减少等待的原则)

如果有A/B/C/D四个人,且耗时A

  • 最快的来回送人方式,A+B去;A回;A+C去,A回;A+D去; 总耗时是B+C+D+2A (减少等待原则)
  • 最快和次快一起送人方式,A+B先去,A回;C+D去,B回;A+B去;总耗时是 3B+D+A (减少浪费原则)

对比方案1、2的选择,我们发现差别仅在A+C和2B;

为何方案1、2差别里没有D?

因为D最终一定要过河,且耗时一定为D。

如果有A/B/C/D/E 5个人,且耗时A

仍是从最慢的E看。(参考我们无限多船的情况)

  • 方案1,减少等待;先送E过去,然后接着考虑四个人的情况;
  • 方案2,减少浪费;先送E/D过去,然后接着考虑A/B/C三个人的情况;(4人的时候的方案2)

到5个人的时候,我们已经明显发了一个特点:问题是重复,且可以由子问题去解决。

根据5个人的情况,我们可以推出状态转移方程dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);

再根据我们考虑的1、2、3、4个人的情况,我们分别可以算出dp[i]的初始化值:

dp[1] = a[1];  dp[2] = a[2];  dp[3] = a[2]+a[1]+a[3];  dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]); 

由上述的状态转移方程和初始化值,我们可以推出dp[n]的值。

这是一道贪心和动态规划的结合题目,动态规划的决策过程中用到了贪心的策略。

总结

贪心的学习过程,就是对自己的思考进行优化。

是把握已有信息,进行最优化决策。

这里还有一些收集的贪心练习题,可以实践练习。

原文发布于微信公众号 - 程序你好(codinghello)

原文发表时间:2018-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

地图可视化之——移花接木

本文所使用的代码是之前一篇关于航线图的数据,之所以要从新写一遍,是为了让大家体会借助在线地图制作地图可视化在代码效率上的便利(当然,也会有损失,你不能像操纵sh...

37760
来自专栏后台全栈之路

《ArcGIS 地理信息系统教程》概念笔记

之前研究了 GIS,接触到了很多 GIS 的概念。因此找了《 ArcGIS 地理信息系统教程(第 4 版)》来看。书的版本比较老了,不过一些基本概念还是想通的,...

32560
来自专栏ATYUN订阅号

赫尔辛基大学AI基础教程:搜索和解决问题(2.1节)

想象一下你在一个外国的城市,在某个地方(比如一家酒店),想用公共交通工具去另一个地方(比如一家不错的餐馆)。你是做什么?如果你会像许多人一样,掏出智能手机,输入...

15460
来自专栏玩转全栈

机器学习-数据清洗(二)

如果接触到我上面的那篇文章,机器学习-入门,应该很清楚本文意欲为何。如果不知道为什么,请阅读一下那篇文章,以便打下基础,ok,废话不多说了,进入正题。

38410
来自专栏新智元

【20张图玩转机器学习】深度学习、神经网络和大数据信息梳理(下载)

【新智元导读】ChatbotLife 的创始人兼编辑 Stefan Kojouharov 收集并整理了一系列 AI 相关的信息图示,为了便于使用,还附带了注释和...

43850
来自专栏数据派THU

一文带你入门图论和网络分析(附Python代码)

本文从图的概念以及历史讲起,并介绍了一些必备的术语,随后引入了networkx库,并以一个航班信息数据集为例,带领读者完成了一些基本分析。

58220
来自专栏杨建荣的学习笔记

字符画,你可能未知的美 (76天)

在平时的工作中,如果接触字符界面时间比较长的时候,都会无意识的感觉到单调,认为字符只能表达一些抽象复杂的东西,对于图形的那种简单和清晰,显得有些力不从心。 今天...

31550
来自专栏数据小魔方

R语言可视化——ggplot图表配色技巧

今天跟大家分享ggplot图表的配色原理与基本技巧。 图表配色是一个很深奥的话题,多亏了R语言平台的众多开发者贡献的配色包,让图表的配色不再深不可测。 这里我暂...

71140
来自专栏用户画像

相似人群画像算法

由于TESLA集群无法直接操作MongoDB,需要将TDW里面的用户画像数据,通过洛子系统导出至HDFS,再与MongoDB中原有群画像进行合并。

72750
来自专栏北京马哥教育

Python自然语言处理分析倚天屠龙记

? 转载自:Python中文社区 ID:python-china 最近在了解到,在机器学习中,自然语言处理是较大的一个分支。存在许多挑战。例如: 如何...

49560

扫码关注云+社区

领取腾讯云代金券