专栏首页云时之间算法导论系列:贪心算法(1)

算法导论系列:贪心算法(1)

周末开始着手算法这一系列文章,说起写这一系列的初衷是发现网上很多的同学们在学习算法这个时候,会遇到很多困难,而学校书中讲的道理尽管很对,但是总是太过于晦涩,正确的知识总是晦涩,这点没错,但让晦涩的知识变得有趣岂不是也很有意思?回想起自己学习算法的过程中,遇到了不少的坑坑.特想写一些文章去记录下自己过程中的所思说想,也借这些文章自己复习学习一下.

这系列文章主要包括几个大类的算法,包括贪心算法,分治法,动态规划,回溯法,分支定界法,线性规划法等等,具体在这些大类算法内每次会选几个小例子去加深意识,并且会给出能够运行的代码来!这一点看起来很好笑,但是很重要,很多同学在看课本的时候都说算法书上的代码都不能运行,太讨厌了,实际上书上是需要你理解算法而不是理解代码.但是能够运行的代码同样也有意义,能够让人迅速获得喜悦和自信,当然理解也需要下一些苦功夫.

正文开始:

贪心算法其实本身就跟我们人性一样,看到眼前的好吃的,拿来拿来别客气.但是丝毫不顾忌自己还得燃烧卡路里.贪心算法也是这样.

贪心算法的本质其实就是总是做出当前最好的选择,也就是说算法总是期望通过局部最优选择从而得到全局最优的解决方案.

但是大家想想贪心算法其实是很”目光短浅”的,因为仅仅根据当前眼下的信息来做出决策,这样就不是从整体来最优考虑,他做出的选择只能是某种意义上的局部最优.但是,贪心算法可以得到很多问题的整体最优解或者近似解,在实际生活中还是有一定的意义的,因此贪心算法还是得到了广泛的应用.

但是贪心也不是全部都要,贪心的算法也是有一定的原则,经过我们很多的实践后发现,要想利用贪心算法解决问题,必须要满足两个性质:

1:贪心选择

所谓的贪心选择其实是说原问题可以分解成一个个的小问题来去求解,小问题的结果合成之后一样是原问题的结果,这样保证了每一步都是当前最佳的选择,并且程序运行中没有回溯过程.

2:最优子结构

最优子结构其实是说当一个问题的最优解包含其子问题的最优解时,称此问题拥有最优子结构,问题能否拥有最优子结构其实是可否利用贪心算法的关键.

现在我们用一个例子说一下贪心算法:

现在我们有一批货物,货物的重量w和价值v都是不固定的,但是我们货车的运载量是固定的,只有m,但是货物可以分割,因此怎么样可以让运载的货物价值最大呢?

现在我们有三种思路:

1:拣价值最高的货物来运输,肯定赚

2:拣重量最小的货物来运输,也不亏

3:选择性价比(价值/重量)大的货物来运输,看起来不错

这三种方法想想也是第三种合理,第一种的尽管价值最大,但是如果货物的重量也是非常大,这就不划算了,如果选重量最小的货物,如果卖不上价格,岂不也是很亏,因此,每次选择性价比最高的货物,不失为一个优秀的选择.

那让我们设计一下算法:

1:数据结构及其初始化

我们这次使用结构体的方式,将n种货物的重量,价值以及性价比存储在结构体当中,并且使用将其按照性价比的高低来将其排序,

2:贪心策略

根据贪心策略,我们优先选择性价比高的货物,并且每次放入后与运载能力m进行比较,求出最大值即可.

现在我们贴出代码:

在代码中输入样例:

运行结果如下:

下一篇文章我们将说说使用Dijkstra算法解决最短路径问题,这也是贪心算法的一种,也是挺有意思的,还请多多指教.

参考资料:

1:大话数据结构,清华大学出版社

2:算法导论,机械工业出版社

3:趣学算法,人民邮电出版社

4:算法分析,人民邮电出版社

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • 计算机网络自学笔记:选路算法

    网络层必须确定从发送方到接收方分组所经过的路径。选路就是在网络中的路由器里的给某个数据报确定好路径(即路由)。

    云时之间
  • 算法导论系列:贪心算法(2)

    现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

    云时之间
  • Day9 :变态跳台阶

    背景知识介绍   贪心算法相信大家都听说过,但是大家或许没有系统的了解过。这是维基百科对贪心算法介绍:贪心算法 (greedy algorithm) ,又称贪...

    stefan666
  • 经典算法之贪心算法

      贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优解出发来考虑,它所做出...

    用户3467126
  • 基于图像分割的立体匹配方法

    立体匹配是三维重建系统的关键步骤,并且作为一种非接触测量方法在工业以及科研领域具有重要的应用价值。为了完成匹配工作以及获取场景的稠密视差图,可以通过构建能量函数...

    流川疯
  • 数据结构 | 每日一练(1)

    ——老子

    C语言入门到精通
  • 重构 改善既有代码的设计--笔记

    查看一个类是否“过大”,这里有一个小技巧分享给大家。就是看两点:1)这个类实例变量太多,必然会有Duplicated Code(重复代码) 2)类内如果有太多代...

    哲洛不闹
  • 算法眼中的世界是什么样子?他们用一些彩色方块画了出来

    安妮 编译自 Wired 量子位 出品 | 公众号 QbitAI 从数字助手、加密数字货币到自动驾驶汽车,算法在生活中无处不在。 这是个抽象的概念,对于不了解人...

    量子位
  • 新手入门 | 算法书籍推荐

    公众号设立以来,很多同学都在问如何入门、提高,以及有什么好的算法书籍可以学习。这周空闲时间我就大概在网上整理了一下,由于每个人的性格、学习习惯都不...

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券