贪心算法是什么?贪心算法如何解决问题?

你可能不知道贪心算法,但你一定知道活在当下。如果你知道,那么恭喜你,你已经掌握贪心算法的核心本质了!

贪心算法的理念就是不问过去,不计将来,只考虑当下。捡了芝麻丢了西瓜?不存在的!当下有西瓜,绝不碰芝麻~

贪心算法讲究的是每遇到一个子问题, 都取当下情况的最优解, 直到所有子问题被解决。

那么,贪心算法到底是怎么帮我们解决问题的呢?

购买了一张戛纳电影节的一日票。双程机票、翻倍的酒店价格都让我的钱包越来越扁... 心痛 .jpg... 为了能最大限度薅到资本主义的羊毛,我当然会爆发出爱因斯坦的智商,来精准计算怎样的观影顺序能让我在有限的时间里看到最多的电影!传奇天主教总统传记《肯尼迪传》,小李子《花月杀手》,北野武的《首》还有缠绕三角恋《燃东》-- 统统到我碗里来!!

假设:当天有 n 部电影,第 i 部电影在 a 时开始、b 时结束。每部电影都可以选择看或不看。但如果选择看某部电影,那即使遇到烂片也必须全程看完。并且不能同时观看 2 部及 2 部以上电影。

求:我最多能看几部电影?

很显然,这道题的子问题就是:从某个时刻起,应该如何选择下一场电影?

可以有以下选择:

1、当天每次都选开始时间最早的电影;

2、当天每次都选结束时间最早的电影;

3、当天每次都选用时最短的电影;

4、当天每次都选与最少可选工作有重叠的电影。

根据以下图示,很容易证明选择 1,3,4 是不可行的!

戛纳电影节在即,如何用计算机贪心算法将所爱一网打尽!戛纳电影节在即,如何用计算机贪心算法将所爱一网打尽!戛纳电影节在即,如何用计算机贪心算法将所爱一网打尽!

由此可见,子问题的最优解就是:每次都选结束时间最早的电影!

这就是此题的贪心策略,可选电影中结束时间最早的那场电影就是本题的局部最优解。

由于每场电影包含一个开始时间和一个结束时间,所以我们可以定义一种结构体,命名为 Movie

Movie 中包含了开始时间和结束时间,代码如下:

戛纳电影节在即,如何用计算机贪心算法将所爱一网打尽!

总结:

  • 贪心法就是指在求解问题时,总是做出当前最好的选择(而不是整体)。
  • 贪心算法没有固定的框架,算法设计的关键是贪心策略的选择。
  • 贪心策略必须具备无后效性,即某个状态的选择只与当前状态有关。

小课堂

在我看来,每个人每天都在做“贪心算法”。

我们的人生都是由无数个子问题构成的,我们需要在无数个小的路口做出我们认为对的选择,但生活无法回头,即使后来我们知道我之前的选择可能并非最优解,可我们也无法从头来过。没有人可以穿越回去修改过去的选择,从而获得“全局的绝对最优解”。

因为我知道我永远只能基于当下的认知水平,在不完美的条件下做我认为最利于当下的选择,而不是在理想情况下做最优解,抱怨“为什么条件不完美”是没有意义的。不完美是人生的常态,我能做到的,只有不埋怨现状,不害怕未来,尽量不断地做出我认为对的选择。

不要将自己困囿于过去的错误中,也不要惧怕未来,抓住每一个小时做贪心算法吧!

【竞赛报名/项目咨询请加微信:mollywei007】

微信扫一扫,分享到朋友圈

贪心算法是什么?贪心算法如何解决问题?
上一篇

DS专业、CS专业、BA专业哪个更适合?

下一篇

2023年最新第74届ISEF获奖作品全面剖析!

你也可能喜欢

  • 暂无相关文章!

关注热点

返回顶部