【贪心算法】思想 & 基本要素 & 贪心算法与局部最优 & 贪心算法与动态规划的区别 & 运用贪心算法求解问题
首先我们先代入问题来认识一下贪心算法涉及的问题
找钱问题
给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定
找钱问题满足最优子结构
最快找零（贪心）：为得到最小的找零次数，每次最大程度低减少零额活动安排问题
设个活动都需要使用某个教室，已知它们的起始时间和结束时间，求合理的安排使得举行的活动数量最多
贪心：使得每次安排后，教室的空闲时间最多
解决过程如下：
贪心算法求得的相容活动集是最大的
第一步：证明最优解中包含结束时间最早的活动
设相容集 A 是一个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是一个最优解
第二步：证明去掉结束时间最早的活动后，得到的子问题仍是最优的：反证法
理解贪心算法
贪心算法总是做出当前最好的选择
贪心选择的依据是当前的状态，而不是问题的目标
贪心选择是不计后果的
贪心算法通常以自顶向下的方法简化子问题
贪心算法求解的问题具备以下性质
贪心选择性质：问题的最优解可以通过贪心选择实现
最优子结构性质：问题的最优解包含子问题的最优解
贪心选择性质的证明
证明问题的最优解可以由贪心选择开始
即第一步可贪心
证明贪心选择后得到的子问题满足最优子结构
即步步可贪心
背包问题
问题描述：给定 n 个物品和一个背包。
物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的一部分，使得背包中物品的价值最大？
当 n = 3 ，c = 50
0-1背包问题：装入物品2、3，最大价值220
背包问题：装入物品1、2和2-3的物品3，最大价值240（贪心算法）贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2
贪心与局部最优
思考：为什么0-1背包可以用动态规划？而不能用贪心算法
贪心易陷入局部最优
好比“以最快的速度下山”，每步都选择最快不见得一定到达山脚
局部最优是指解在一定范围或区域内是最优的，或求解问题的方法在一定限制条件下是最优的
一般的启发式算法、贪心算法或局部算法都很容易产生局部最优
局部最优通常是无法查证的
获得局部最解的复杂度远低于全局最优解
找钱问题：15元找零11之后，不存在面值为4元的零钱
0-1背包问题：50容量的背包装入前两个物品仍剩余20容量的空间活动安排问题：若限制教室使用的总时间
贪心算法与动态规划
贪心算法和动态规划都具有最优子结构
贪心算法是自顶向下的，只查看了当前状态；而动态规划自底向上地求解了最优解包含的所有子问题
最优装载
问题描述：一批集装箱要装上一艘载重量为 c 的轮船，其中集装箱 i 的重量为 Wi ，不考虑体积，将尽可能多的集装箱装上轮船贪心：重量轻者先装
思考：与0-1背包问题有什么不同？
设 x = (x1, x2, … , xn) 是最优装载问题的最优解（贪心算法）贪心选择性质：设y = (y1, y2, … , yn) 是一个最优解，其第一个不为0的选择为 yk = 1，则将物品 k 替换成物品1，仍满足容量限制，替换方案就构成了原问题的另一个最优解
最优子结构性质：考虑去掉物品1后的子问题
哈夫曼编码
Huffman编码是一种可变字长编码，一种构建极小多余编码的方法
一篇包含6种字符的文档中
将串001011101解码为aabe
定义平均码长为
求文档 C 的哈夫曼编码就等价于构建一棵最优完全二叉树，使得平均码长最小
即文档 C 的最优前缀码
贪心算法：依次将最小频率的节点两两合并
单源最短路径
问题描述：设一个带权的有向图 G = （V， E）
求从源顶点 V1属于 V 到其他顶点的最短路径
Dijkstra 算法又称为标号法
T标号：临时标号（tentative label），表示到源顶点的路径还可以进一步降低，有待探查
P标号：永久标号（permanent label），表示已经找到源顶点的最短路径，不再探查
当所有顶点的标号变成P标号时，算法结束，即算法最多需要 n - 1 步初始：给起点一个 P 标号 0，其他顶点为无穷大的 T 标号
更新：若顶点 Vi 最近获得了P标号，考查与其有弧 eij 相连的顶点Vj，若 Vj 仍是 T 标号，更新其 T 标号为
决策：在所有 T 标号中，选择一个值最小的顶点，令其变为 P 标号Dijkstra 算法为什么没有陷入局部最优？
贪心：决策总是在所有T标号的顶点中选择最小
最小生成树
给定无向图 G = （V， E），称G‘ = （V’，E‘）是 G 的一个子图，若V’ 包含于 V，E’包含于 E。
若V’ = V，则称G‘ 是 G 的一个支撑子图
若一个无向图是连通的，且无回路，则称这个图为一个树
给定图 G ，若 G 的一个支撑子图 T 是一个树，则称 T 为 G 的一个支撑树
若 G 是一个带权的图，则称权最小的支撑树为 G 的最小生成树
Most Small Tree：设 G = （V， E）是一个连通带权图，设 (u , v) 包含于 E， u 包含于 U，v 包含于 V - U，其中 U 属于 V ，且 (u , v) 是这样的边中权最小的一条边，则一定存在 G 的一棵最小生成树包含 (u , v) 这条边
贪心：每次选取已观察顶点集与未观察顶点集之间具有最小权的边，将所有边按权从小到大排序，依次添加到最小生成树中，且不形成回路多机调度问题
问题描述：给定 n 个独立的作业要在 m 台机器上加工，求合理的调度方案使得加工时间最短
贪心：将最长时间的作业安排到最闲的机器上
贪心选择：
只剩一个作业时，应安排在最闲的机器上
最后安排时间最短的作业
贪心算法总是选择当前最有利的方案，因而容易陷入局部最优解
贪心算法可解的问题应具有贪心选择性质和最优子结构性质
贪心算法的证明分两步，第一步证明可将最优解替换成以贪心选择开始，第二步证明去掉贪心选择后满足最优子结构
贪心算法的复杂性很低
贪心算法无法求解0-1背包问题，按贪心算法，0-1背包问题将装入物品1和2
服务问题我们现在的每个人接受服务的时间就是自己和之前所有人时间的总和，而当更高一级的客户来的时候就会自动地排在现在接受服务的人的后面，后面所有的人次序就会自动的像后面加一。
b[k].vlue=a[i].s; b[k++].flag=0;--0代表开始时间
printf("%d,%d",a[i].start,a[i].finish);
}。
这些活动使用同一个资-源（如教室）。
该资-源一次只能被一个活动占用。
每个活动
if(courses[max_i][0] courses[i][0]){
时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解。
（2）建立数组 dist[i]，存源到 i 点的距离。
若源与点 i 直接相连，则 dist[i] 等于权重，若源与 i 不直接相连，则dist[i]=∞。
1．若a[i]v，则将a[i]-v张从第I堆移动到第I+1堆；
result.append(goods(a_goods.id, capacity, a_goods.value * capacity - a_goods.weight))。