算法读书笔记-3

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~

贪心算法

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择得到全局最优的解决方案。
——《算法导论》

贪心算法正是“活在当下，看清楚眼前”的办法。贪心算法从问题的初始解开始，一步一步地做出当前最好的选择，逐步逼近问题的目标，从而尽可能地得到最优解，即使达不到最优解，也可以得到最优解的近似解。

对于贪心算法，需要注意以下几个问题。
(1）一旦做出选择，就不可以回溯。
(2）有可能得不到最优解，而是得到最优解的近似解。
(3）选择什么样的贪心策略直接决定算法的好坏。

1.性质

1.1贪心选择

贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。

1.2 最优子结构

最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。例如，对于原问题S={a1，a2，…，ai，…， an}，可以在通过贪心选择得到一个当前最优解(ai}之后，转换为求解子问题S-{ai}，继续求解该子问题，最后对所有子问题的最优解进行合并，即可得到原问题的最优解。

2.最优装载问题

2.1 问题描述

海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。海盗船虽然足够大，但载重量是有限的。海盗船的载重量为W，每件古董的重量为wi，如何才能把尽可能多的古董装上海盗船呢？

2.2思路分析

问题要求装载的古董尽可能多，在载重量有限的情况下，优先把重量小的古董装进去，装的古董最多。可以采用重量最小者先装的贪心策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。

2.3算法设计

贪心策略是重量最小的古董先装，每次从余下的古董中选择一个重量最小的古董。如果采用顺序查找法寻找最小值，则n个元素最多需要比较n次。第1次选择时有n个古董，需要比较n次；第2次选择时有n-1个古董，需要比较n-1次；.；第n次选择时需要比较1次，总共需要比较n(n+1)/2次，时间复杂度为O(n2）。如果采用快速排序法寻找最小值，也就是先从小到大排序，再按顺序选择，则时间复杂度为O(nlogn)，相比顺序查找法更优。在序列没有变化（静态）的情况下，如果需要多次从序列中选择最小值或最大值，那么可以采用先排序的办法，这样效果更好。
(1）把n个古董的重量从小到大（非递减）排序。
(2）根据贪心策略选择装入的古董，直到不能继续装为止，此时达到最优。
** 如果还行继续了解更多的算法题目** 可通过下面的活动链接查看耿多
14天阅读挑战赛