贪⼼算法1、如何理解贪⼼算法贪⼼算法的思想是:每次都做出当前最优的选择，通过多步选择得出最终的最优解。
它适合解决上⼀步的选择不会影响下⼀步的选择的问题。
如果上⼀步的选择会影响下⼀步的选择，则使⽤贪⼼算法不⼀定能求出最优解。
1.1 能够使⽤贪⼼算法求解的问题举例问题：假如我们有⼀个能够容纳100Kg物品的袋⼦，可以装各种物品，不管物品的体积。
现在我们有5种⾖⼦，每种⾖⼦的总重量和总价值各不相同。
那如何往背包⾥⾯装这些⾖⼦，使得最后背包⾥物品的总价值最⼤呢？我们⼀眼就能知道这个问题的解法，先求出每种⾖⼦的单价，然后从单价⾼的⾖⼦开始装，装完单价⾼的，再去装次⾼的，直到袋⼦装满为⽌。
这个问题就适合⽤贪⼼算法来解，实际上上⾯的做法体现的就是贪⼼算法的思想（每次都做出当前最优的选择）。
这⾥第⼀步选择装单价最⾼的⾖⼦之后，不会影响第⼆步去选择装次⾼的⾖⼦的选择，同样第⼆步也不会影响第三步去选择单价排名第三的⾖⼦。
1.2 不能使⽤贪⼼算法来求解的问题举例问题：假如我们要在⼀个有权图中，从顶点S开始，找⼀条到顶点T的最短路径。
贪⼼算法的解决思路是，每次都选择⼀条根当前顶点相连的权最⼩的边（每次都做出当前最优的选择），直到找到顶点T。
按照这种思路，我们求出的最短路径是S->A->E->T,路径长度1+4+4=9;⽽实际的最短路径是S->B->D->T，路径长度2+2+2=6 。
为什么这⾥贪⼼算法得不到最优解呢？我们第⼀步从S->A和第⼀步从S->B，下⼀步⾯对的顶点和边是不⼀样的。
也就是我们前⾯的选择会影响后⾯的选择，所以得不出最优解。
⽐如：钱币找零'''假设现在市⾯上有 6 种不同⾯值的硬币，各硬币的⾯值分别为 5 分、1 ⾓、2 ⾓、5 ⾓、1 元、2 元，要找零 10.5 元，求出最少硬币的数量。
'''def getChange(coins, amount):coins.sort();# 从⾯值最⼤的硬币开始遍历i = len(coins)-1while i >= 0:if amount >= coins[i]:n = int(amount // coins[i])change = n * coins[i]amount -= changeprint (n, coins[i])i -= 1getChange([0.05,0.1,0.2,0.5,1.0,2.0], 10.5)再⽐如：使⽤贪⼼算法实现哈夫曼编码3.1 什么是哈夫曼编码哈夫曼编码是⼀种⼗分有效的编码⽅法，⼴泛应⽤于数据压缩中，其压缩率通常在20%~90%之间。
贪心算法的基本原理贪心算法（Greedy Algorithm）是一种常用的算法思想，它在求解最优化问题时通常能够得到较好的近似解。
贪心算法的基本原理是：每一步都选择当前状态下的最优解，从而希望最终能够得到全局最优解。
在实际应用中，贪心算法常常用于解决一些最优化问题，如最小生成树、最短路径、任务调度等。
一、贪心算法的特点贪心算法具有以下特点：1. 简单：贪心算法通常比较简单，易于实现和理解。
2. 高效：贪心算法的时间复杂度通常较低，能够在较短的时间内得到结果。
3. 局部最优：每一步都选择当前状态下的最优解，但不能保证最终能够得到全局最优解。
4. 适用范围：贪心算法适用于一些特定类型的问题，如无后效性、最优子结构等。
二、贪心算法的基本原理贪心算法的基本原理可以概括为以下几个步骤：1. 初始状态：确定问题的初始状态，定义问题的输入和输出。
2. 状态转移：根据当前状态，选择局部最优解，并更新状态。
3. 筛选解：判断当前状态下是否满足问题的约束条件，若满足则保留该解，否则舍弃。
4. 终止条件：重复以上步骤，直至满足终止条件，得到最终解。
三、贪心算法的应用举例1. 找零钱：假设有 25、10、5、1 四种面额的硬币，需要找零 41 元，如何使得找零的硬币数量最少？贪心算法可以先选择面额最大的硬币，然后逐步选择面额较小的硬币，直至找零完毕。
2. 区间调度：给定一组区间，如何选择最多的互不重叠的区间？贪心算法可以先按照区间的结束时间排序，然后依次选择结束时间最早的区间，直至所有区间都被覆盖。
3. 最小生成树：在一个连通的带权无向图中，如何选择边使得生成树的权值最小？贪心算法可以按照边的权值从小到大排序，然后依次选择权值最小且不构成环的边，直至所有顶点都被连接。
四、贪心算法的优缺点1. 优点：贪心算法简单高效，适用于一些特定类型的问题，能够在较短的时间内得到近似最优解。
2. 缺点：贪心算法不能保证一定能够得到全局最优解，可能会出现局部最优解不是全局最优解的情况。
贪⼼算法【贪⼼算法】思想 & 基本要素 & 贪⼼算法与局部最优 & 贪⼼算法与动态规划的区别 & 运⽤贪⼼算法求解问题⾸先我们先代⼊问题来认识⼀下贪⼼算法涉及的问题找钱问题给顾客找钱，希望找零的钞票尽可能少，零钱种类和数量限定找钱问题满⾜最优⼦结构最快找零（贪⼼）：为得到最⼩的找零次数，每次最⼤程度低减少零额活动安排问题设个活动都需要使⽤某个教室，已知它们的起始时间和结束时间，求合理的安排使得举⾏的活动数量最多贪⼼：使得每次安排后，教室的空闲时间最多解决过程如下：贪⼼算法求得的相容活动集是最⼤的第⼀步：证明最优解中包含结束时间最早的活动设相容集 A 是⼀个最优解，其结束最早的活动为 a，则 ( A - { a }) U { 1 } 也是⼀个最优解第⼆步：证明去掉结束时间最早的活动后，得到的⼦问题仍是最优的：反证法理解贪⼼算法贪⼼算法总是做出当前最好的选择贪⼼选择的依据是当前的状态，⽽不是问题的⽬标贪⼼选择是不计后果的贪⼼算法通常以⾃顶向下的⽅法简化⼦问题贪⼼算法求解的问题具备以下性质贪⼼选择性质：问题的最优解可以通过贪⼼选择实现最优⼦结构性质：问题的最优解包含⼦问题的最优解贪⼼选择性质的证明证明问题的最优解可以由贪⼼选择开始即第⼀步可贪⼼证明贪⼼选择后得到的⼦问题满⾜最优⼦结构即步步可贪⼼背包问题问题描述：给定 n 个物品和⼀个背包。
物品 i 的重量为 Wi ，价值为 Vi ，背包的容量为 c ，问如何选择物品或物品的⼀部分，使得背包中物品的价值最⼤？当 n = 3 ，c = 500-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。
