周末开始着手算法这一系列文章,说起写这一系列的初衷是发现网上很多的同学们在学习算法这个时候,会遇到很多困难,而学校书中讲的道理尽管很对,但是总是太过于晦涩,正确的知识总是晦涩,这点没错,但让晦涩的知识变得有趣岂不是也很有意思?回想起自己学习算法的过程中,遇到了不少的坑坑.特想写一些文章去记录下自己过程中的所思说想,也借这些文章自己复习学习一下.
这系列文章主要包括几个大类的算法,包括贪心算法,分治法,动态规划,回溯法,分支定界法,线性规划法等等,具体在这些大类算法内每次会选几个小例子去加深意识,并且会给出能够运行的代码来!这一点看起来很好笑,但是很重要,很多同学在看课本的时候都说算法书上的代码都不能运行,太讨厌了,实际上书上是需要你理解算法而不是理解代码.但是能够运行的代码同样也有意义,能够让人迅速获得喜悦和自信,当然理解也需要下一些苦功夫.
正文开始:
贪心算法其实本身就跟我们人性一样,看到眼前的好吃的,拿来拿来别客气.但是丝毫不顾忌自己还得燃烧卡路里.贪心算法也是这样.
贪心算法的本质其实就是总是做出当前最好的选择,也就是说算法总是期望通过局部最优选择从而得到全局最优的解决方案.
但是大家想想贪心算法其实是很”目光短浅”的,因为仅仅根据当前眼下的信息来做出决策,这样就不是从整体来最优考虑,他做出的选择只能是某种意义上的局部最优.但是,贪心算法可以得到很多问题的整体最优解或者近似解,在实际生活中还是有一定的意义的,因此贪心算法还是得到了广泛的应用.
但是贪心也不是全部都要,贪心的算法也是有一定的原则,经过我们很多的实践后发现,要想利用贪心算法解决问题,必须要满足两个性质:
1:贪心选择
所谓的贪心选择其实是说原问题可以分解成一个个的小问题来去求解,小问题的结果合成之后一样是原问题的结果,这样保证了每一步都是当前最佳的选择,并且程序运行中没有回溯过程.
2:最优子结构
最优子结构其实是说当一个问题的最优解包含其子问题的最优解时,称此问题拥有最优子结构,问题能否拥有最优子结构其实是可否利用贪心算法的关键.
现在我们用一个例子说一下贪心算法:
现在我们有一批货物,货物的重量w和价值v都是不固定的,但是我们货车的运载量是固定的,只有m,但是货物可以分割,因此怎么样可以让运载的货物价值最大呢?
现在我们有三种思路:
1:拣价值最高的货物来运输,肯定赚
2:拣重量最小的货物来运输,也不亏
3:选择性价比(价值/重量)大的货物来运输,看起来不错
这三种方法想想也是第三种合理,第一种的尽管价值最大,但是如果货物的重量也是非常大,这就不划算了,如果选重量最小的货物,如果卖不上价格,岂不也是很亏,因此,每次选择性价比最高的货物,不失为一个优秀的选择.
那让我们设计一下算法:
1:数据结构及其初始化
我们这次使用结构体的方式,将n种货物的重量,价值以及性价比存储在结构体当中,并且使用将其按照性价比的高低来将其排序,
2:贪心策略
根据贪心策略,我们优先选择性价比高的货物,并且每次放入后与运载能力m进行比较,求出最大值即可.
现在我们贴出代码:
在代码中输入样例:
运行结果如下:
下一篇文章我们将说说使用Dijkstra算法解决最短路径问题,这也是贪心算法的一种,也是挺有意思的,还请多多指教.
参考资料:
1:大话数据结构,清华大学出版社
2:算法导论,机械工业出版社
3:趣学算法,人民邮电出版社
4:算法分析,人民邮电出版社