关键词：
通常用于最优化问题，我们做出一组选择来达到最优解。每步都追求局部最优。对很多问题都能求得最优解，而且速度比动态规划方法快得多。
16.1 活动选择问题
按结束时间排序，然后选择兼容活动。
定理16.1 考虑任意非空子问题Sk，令am是Sk中结束时间最早的活动，则am在Sk的某个最大兼容活动子集中。
16.2 贪心算法原理
设计贪心算法步骤：
1》将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
2》证明作出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3》证明作出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
贪心选择性质：
我们可以通过做出局部最优（贪心）选择来构造全局最优解。
动态规划：依赖子问题的解。自底向上或自顶向下，都需要先求解子问题。
贪心算法：进行选择时可能依赖之前的选择，但不依赖将来的选择或子问题的解。在进行第一次选择前不求解任何子问题。自顶向下。
如果进行贪心选择时我们不得不考虑众多选择，通常意味着可以改进贪心选择，使其更为高效。通过对输入进行预处理或者使用适合的数据结构（通常是优先队列），通常可使贪心选择更快速。
最优子结构：
如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心算法的关键要素。
贪心对动态规划：
0-1背包问题（动态规划）和分数背包问题（贪心算法）
16.3 赫夫曼编码
前缀码：没有任何码字是其他码字的前缀。前缀码可以保证达到最优数据压缩率。
文件的最优编码方案总是对应一棵满（full)二叉树。即每个非叶结点都有两个孩子结点（国内外教程定义不一致，国内还要求同时是完全二叉树）。
若C为字母表且所以字符的出现频率均为正数，则最优前缀码对应的树恰有|C|个叶节点，每个叶节点对应字母表中的一个字符，且恰有|C|-1个内部结点。
引理16.2 令C为一个字母表，其中每个字符c属于C都一个频率c.freq。令x和y是C中频率最低的两个字符。那么存在C的一个最优前缀码，x和y的码字长度相同，且只有最后一个二进制位不同。
引理16.3 令C为一个字母表，其中每个字符c属于C都一个频率c.freq。令x和y是C中频率最低的两个字符。令C‘为C去掉字符x和y，加入 一个新字符z后得到的字母表，即C‘=C-{x,y}U{z}。类似C，也为C‘定义freq，不同之处只是z.freq=x.freq+y.freq。令T‘为字母表C‘的任意一个最优前缀码对应的编码树。于是我们可以将T‘中叶节点z替换为一个以x和y为孩子的内部结点，得到树T，而T表示字母表C的一个最优前缀码。
16.4 拟阵和贪心算法
16.5 用拟阵求解任务调度问题
算法导论_第十六章_动态规划_creatshare分享会
...结果储存下来，再次用到的时候就不必再进行重复计算。算法导论对 查看详情
《算法导论》读书笔记
前言：贪心算法也是用来解决最优化问题，将一个问题分成子问题，在现在子问题最优解的时，选择当前看起来是最优的解，期望通过所做的局部最优选择来产生一个全局最优解。书中先从活动选择问题来引入贪心算法，分... 查看详情
软件工程导论第十六章随笔
第一章 通过阅读第一章，使我对软件工程有了更加深刻的认识，从软件的定义到发展，再到具体实现一个令大众满意的软件的流程和软件开发的各个阶段都有很详细的介绍，更是引用了航空产业的... 查看详情
算法导论读书笔记-第十三章-红黑树
算法导论第13章红黑树红黑树(red-blacktree)是许多平衡搜索树中的一种,可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lgn).13.1红黑树的性质红黑树(red-blacktree):满足下面性质的二叉搜索树:每个结点是红色的或者黑色的.根... 查看详情
算法导论笔记——第十二~十四章数据结构树
...TE可以在O(h)时间内完成。h>=（lgn向下取整）和快速排序算法一样，其平均性能更接近于最好情形。随机构建二叉搜索树期望高度为O(lgn). 各种 查看详情
算法导论笔记——第十五章动态规划
通常用来解决最优化问题。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会非常有效。其关键技术就是对每个这样的子问题都保存其解，当其... 查看详情
第十六章-序列号生成算法分析-part1（上）(代码片段)
步骤：1、查看CrackMe程序信息2、使用OllyDbg加载CrackMe程序3、GetDlgItemTextA函数设置一个内存断点4、读取输入的序列号的位置5、输入的序列号的值6、输入的序列号计算的值保存在eax寄存器7、程序的计算逻辑8、计算输入的用户... 查看详情
算法导论第十五章
15.115.1-1证明：?T(n)=1+\(\sum_0^n-1T(j)\)?令S(n)=\(\sum_0^nT(j)\)?则S(n)-S(n-1)=1+S(n-1)?S(n)=\(2^n+1\)-1?T(n)=\(2^n\)15.1-2长度i1234价格pi146.54价格密度126.5/31按照贪心策略分割为3、1，总价格为7.5然而最优解为2、2，总价格为815.1-3#inclu 查看详情
算法导论读书笔记-第十四章-数据结构的扩张
算法导论第14章数据结构的扩张一些工程应用需要的只是标准数据结构,但也有许多其他的应用需要对现有数据结构进行少许的创新和改造,但是只在很少情况下需要创造出全新类型的数据结构,更经常的是通过存储额外信息的方法... 查看详情
算法导论笔记——第十~十一章数据结构散列
第十章基本数据结构栈：可由数组表示队列：可由数组表示指针和对象：可由多数组表示。可用栈表示freelist有根数： 二叉树：左右孩子 分支无限制：左孩子右兄弟表示法 第十一章散列表数组：为每个元素保留一个... 查看详情
《构建之法》第十六章阅读笔记
第一章 问题一:1.2.4软件工程的目标--创造"足够好"的软件 什么是好软件? 原文1.一些同学认为，所谓好软件，就是软件没有Bug，所谓软件工程,就是把软件中的Bug都消灭掉的过程。 软... 查看详情
算法导论之贪心算法
...http://www.cnblogs.com/Creator/archive/2011/06/07/2074227.html 贪心算法在几个基本算法里面算是相对简单的算法了，思路也是非常简单的，每一步总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择... 查看详情
《构建之法》读书笔记之：第十六章
...是会有一套详细的流程规范。下面是我看书时的一些心得笔记，和一些无法自己解答的疑惑，烦请各位老师批评指教。 第一章：笔记 查看详情
算法导论——贪心算法(代码片段)
贪心算法（greedyalgorithm）是指，在每一步都做出当时看起来最佳的选择，也就是局部最优的选择，期望这样的选择能够导向全局最优解。所以并不是所有的问题都能得到全局最优解。 典型的例... 查看详情
《java编程思想》学习笔记——第十六章数组
数组和其它种类的容器之间的区别有三方面：效率，类型和保存基本类型的能力。在Java中，数组是一种效率最高的存储和随机访问对象引用序列的方式。数组就是一个简单的线性序列，这使得元素访问非常快... 查看详情
贪心算法算法导论找零问题
...零钱的问题。假设每种硬币的面额都是整数。A.设计贪心算法求解找零问题，假定有25美分、10美分、5美分和1美分4种面额的硬币。证明你的算法能找到最优解。B.假定硬币的面额是c的幂，即面额c0,c1,...,ck,c和k为整数，... 查看详情
《算法导论》第六章练习题exercise
...度为h的堆中，元素最多有2h+1-1个，最少有2h 个。注意算法导论里的高度是指深度，从0开始而不是从1开始。 6.1-2 这很好想，但是不好证明。 由已知高度为h的堆，它的元素个数满足2h <=n<= 2h+1&n... 查看详情
算法导论第六章堆排序
基本过程：1、保持最大堆的性质：假设两个子堆都满足，只需要根节点依次换下去，复杂度O(lgn) 2、初始化堆：后半段都是叶子，在前半段从后往前，依次执行上述最大堆性质的操作，名义复杂度是O(nlgn)，但是有更精确的计... 查看详情