1. 贪心算法
每一步都选择当前状态下的最优解，以期得到结果最优
2. 贪心算法例子：activity selection problem
有一系列的活动ai,(1<i<n)每个活动都有一个开始时间s以及结束时间f，一次只能做一个活动，要求最多可以完成的活动个数
尝试1：活动时间越短跟别的活动冲突的可能性更小，所以每次寻找最短且不会和已经选过的活动冲突的
但是存在反例
尝试2：每次找跟其他活动冲突最小的活动
同样存在反例
正确：在不会和前面已经选择的活动冲突的活动中，选择结束最早的活动
3. proving optimality of a greedy solution
证明所有的最优解都可以被转化为贪心解法，且结果相同
具体步骤为找到第一个违反贪心算法的选择；用贪心算法替代该选择并不会影响结果，也不会造成冲突；重复以上步骤，发现所有最优解均可以转化为贪心解
4. 时间复杂度
对每一个活动用一个tuple记录开始时间与结束时间，然后对每个tuple按照结束时间排序——O(n*log n)
遍历整个list，找到第一个开始时间在已选活动结束时间之后的活动，即记录最后一个已经选择的时间。由于已经根据时间排序了，所以每个活动只会被检测一次，复杂度O(n)
即O(n*log n)
5. 同样一系列活动，每个活动时长均为d，求可完成的最长活动时间
解法同上，因为每个活动时长相同，即可转化为刚才所求出来的最多活动个数乘以统一的时长
6. 若是每项工作都规定了所需要的时间以及deadline，每次只能做一个工作，所有工作都必须完成，若一个工作在deadline之后完成，则lateness等于迟到的时间，任务是使lateness中最大的那项尽可能最小
首先忽略工作所需要的时间，将工作按照deadline升序进行排序
证明同理，对任意最优解，假设一个工作deadline在后面但是被优先完成了，称为一个invertion。若出现invertion，则同等情况下选择贪心算法lateness会更小，则该lateness不是最大lateness，所以可以进行交换
类比冒泡排序，重复走访所有数，如果两个相邻数顺序相反就交换过来，不断重复
7. tape storage
一个磁带中有n个文件，每个文件f都有不同的长度l，每个文件都有相同的机会被用到，使用每一个文件必须从头开始扫描磁带直到找到该文件并且读取结束，任务是对文件排序使得平均读取时间最短
将长度按照递增的顺序排序，由于总时间是l1+(l1+l2)+...+，即前面的时间被重复加了很多次
8. 若是第七题中每个磁带都有p的概率被使用，同样希望时间最短
对pi/li进行排序
9.01 背包算法
有n个物品，每个重wi，价值vi，背包最大容量wi，需要尽可能大的装
不可以用贪心算法解决
分别尝试优先选择价值最高，重量最低的以及最大单位价值的，均不能实现
10. Greedy应用--Huffman code
假设有一系列符号如英文字母和标点符号以及空格，需要用binary string encode加密这些符号使得他们可以被精确解码
方法一：对每个字符都取相同长度的二进制字母表
但是很多bit是浪费的，可能很多0是没有用到的
所以可以进行断句
如何断句使用prefix code，即一个前缀，保证没有一个code是另一个code的前缀
对出现频率最高的字母进行排序，使用二叉树，9024讲过
11. greedy method applied to graphs
用n个塔发布海啸预警，有xy坐标以及辐射半径，一个塔被激活则将激活半径范围内的塔，需要最少的传感器装备这些塔，使得所有塔都接受到海啸预警
尝试1：找到最大半径的未激活的塔，找到后移除所有已经激活的，重复
尝试2：找到半径中有最多的塔未激活的塔，找到后移除所有已经激活的
图包含edge与vertex，图中不能有单独的点
用BFS找到v可达到的所有顶点，以及哪些地方出发可以到v，这些点都是可以互相到达的
在定义一个graph，对有向无环图进行排序