贪心算法入门与实战案例

20XX/XX/XX贪心算法入门与实战案例汇报人:XXXCONTENTS目录01

贪心算法基础概念02

贪心算法适用条件03

贪心算法经典应用场景04

include<iostream><vector><algorithm>\nusingnamespacestd;\nintcoinChange(vector<int>&coins,intamount){\nsort(coins.rbegin(),coins.rend());\nintcount=0,remaining=amount;\nfor(intcoin:coins){if(remaining<=0)break;count+=remaining/coin;remaining%=coin;}\nreturnremaining==0?count:-1;}CONTENTS目录05

经典例题解析：分糖果06

经典例题解析：摇摆数组07

经典例题解析：移除K个数字08

贪心算法解题技巧与总结01贪心算法基础概念贪心算法的核心思想贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法策略，通过局部最优解的累积来期望获得全局最优解。贪心算法的决策特点每一步选择仅依赖当前状态，不考虑未来影响，且一旦做出选择便不可回溯，具有无后效性。贪心算法的形象比喻如同爬山时总是选择当前最陡峭的路径向上攀登，或找零时优先使用最大面额货币，以最快速度接近目标。什么是贪心算法贪心算法的核心思想什么是贪心算法贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）选择的算法策略，通过一系列局部最优选择来期望得到全局最优解。核心策略：局部最优导向全局最优在解决问题时，每一步都只考虑当前状态下的最佳选择，不回溯、不考虑整体，通过逐步构建局部最优解来逼近全局最优解。关键特性：无后效性一旦做出选择，后续决策仅基于当前状态，不受之前选择路径的影响，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。贪心算法的基本步骤问题建模与分解将实际问题抽象为数学模型，拆分成多个连续的局部决策步骤，明确问题的约束条件和优化目标。确定贪心策略明确每一步的“最优标准”，即选择当前状态下最优的选项，如“选最小”“选最大”“选最早结束”等。排序预处理多数贪心问题需要先对数据按策略对应的规则进行排序，以便高效地进行局部最优选择。迭代选择与解构建按照贪心策略逐步选择，构建解决方案，每一步选择后更新问题状态，缩小问题范围或规模。验证解的有效性检查得到的解是否满足问题的约束和要求，确认局部最优选择能否导致全局最优解。贪心算法的关键性质

贪心选择性质问题的全局最优解可以通过一系列局部最优选择（贪心选择）来获得，每次选择只依赖于已做出的选择，不依赖未做出的选择。

最优子结构性质问题的最优解包含其子问题的最优解，即一个问题的最优解可以由其子问题的最优解推导得出，这是贪心算法与动态规划的共同特征。

无后向性某状态以后的过程不会影响以前的状态，贪心策略一旦做出选择就不可回溯，只与当前状态有关，这是贪心算法决策的重要特点。贪心算法与其他算法对比

与动态规划的核心差异贪心算法自顶向下，每步做局部最优选择且不回溯；动态规划通常自底向上，保存子问题解并可回溯比较多种选择。

与回溯法的效率对比贪心算法时间复杂度低（通常O(nlogn)），适合大规模问题；回溯法需枚举所有可能，复杂度高（如O(2^n)），适用于小规模精确解。

适用场景的关键区别贪心适用于具有贪心选择性质和最优子结构的问题（如活动选择、哈夫曼编码）；动态规划适用于重叠子问题和最优子结构问题（如0-1背包）；回溯法适用于解空间小的探索性问题（如排列组合）。

典型问题的算法选择找零钱问题（贪心）、最短路径（Dijkstra贪心/动态规划）、子集和问题（回溯/动态规划）、活动安排（贪心）。02贪心算法适用条件贪心选择性质01贪心选择性质的定义贪心选择性质是指问题的全局最优解可以通过一系列局部最优选择（贪心选择）来获得。即每一步的选择只依赖于已做出的选择，不依赖未做出的选择，且每一步的局部最优选择能导向全局最优解。02贪心选择的核心特征贪心选择具有无后向性，一旦做出选择就不再更改，后续决策仅基于当前状态，不受之前选择路径的影响。它通过逐步构建局部最优解，最终形成全局最优解。03贪心选择性质的判断判断问题是否具有贪心选择性质，需验证局部最优选择能否导致全局最优解。通常可通过反证法或数学归纳法证明，即假设存在更优解，通过替换局部选择推出矛盾，从而证明贪心选择的正确性。04实例：活动选择问题的贪心选择在活动选择问题中，选择结束时间最早的活动作为贪心策略。该选择能为后续活动留出更多时间，通过数学归纳法可证明，此局部最优选择能得到参加活动数量最多的全局最优解。最优子结构的定义问题的最优解包含其子问题的最优解。即，若一个问题的最优解可以通过解决其子问题的最优解来构建，则该问题具有最优子结构性质。最优子结构与贪心算法的关系最优子结构是贪心算法适用的核心条件之一。贪心算法通过每一步的局部最优选择，逐步构建出问题的全局最优解，而这些局部最优解正是子问题的最优解。活动选择问题中的最优子结构在活动选择问题中，若选择了结束时间最早的活动，那么剩余的活动选择问题就是原问题的一个子问题，且该子问题的最优解与已选活动共同构成原问题的最优解。与动态规划的共通性最优子结构也是动态规划算法的重要性质。两者都依赖于子问题的最优解来构建原问题的解，但贪心算法更强调通过局部最优的贪心选择来直接得到全局最优。最优子结构性质问题是否适合贪心算法判断

01判断标准一：贪心选择性质问题的全局最优解可通过一系列局部最优选择（贪心选择）来获得，即每一步的最优选择能导致最终的全局最优。

02判断标准二：最优子结构性质问题的最优解包含其子问题的最优解，即问题可以分解为子问题，子问题的最优解组合起来构成原问题的最优解。

03常见适用场景活动选择、零钱找零（特定货币体系）、分数背包、哈夫曼编码、最小生成树、最短路径（Dijkstra算法）等问题通常适合用贪心算法。

04不适用场景示例0-1背包问题、旅行商问题等不满足贪心选择性质，使用贪心算法无法保证得到全局最优解，需采用动态规划等其他方法。贪心算法的局限性

无法保证全局最优解贪心算法仅关注局部最优选择，可能导致整体解非最优。例如硬币面额为[4,3,1]时，用贪心算法凑6元会选择4+1+1（3枚），而最优解是3+3（2枚）。

适用范围有限仅适用于具有贪心选择性质和最优子结构的问题。如0-1背包问题不适用贪心算法，而分数背包问题可以。

对问题依赖性强问题条件变化可能导致贪心策略失效。例如找零问题中，非标准货币体系（如无1元硬币）可能使贪心算法无法凑出金额。

难以验证正确性需严格证明贪心策略能得到全局最优解，否则可能得到错误结果。实际应用中需通过反例验证或数学证明确保有效性。03贪心算法经典应用场景问题描述给定n个活动，每个活动有开始时间和结束时间，同一时间只能进行一个活动，求最多能选择多少个互不冲突的活动。贪心策略优先选择结束时间最早的活动，为后续活动留出更多时间，从而最大化活动数量。算法步骤1.按结束时间对所有活动从小到大排序；2.选择第一个活动，记录其结束时间；3.遍历后续活动，若当前活动开始时间≥上一个活动结束时间，则选择该活动并更新结束时间；4.统计选择的活动总数。示例说明活动列表：(1,2)、(3,4)、(0,6)、(5,7)、(8,9)、(5,9)，排序后选择(1,2)、(3,4)、(5,7)、(8,9)，共4个活动。活动选择问题零钱找零问题

问题描述给定不同面额的硬币和一个总金额，用最少的硬币数量凑出该金额。假设每种硬币数量无限，且存在1元硬币确保找零可行。

贪心策略每次选择不超过剩余金额的最大面额硬币，尽可能使用大面额硬币以减少总数量。

算法步骤1.将硬币面额按从大到小排序；2.从最大面额开始，计算最多能使用的数量；3.减去已用金额，继续处理剩余金额；4.重复直至金额为0。

C++代码实现单击此处添加项正文04include<iostream><vector><algorithm>\nusingnamespacestd;\nintcoinChange(vector<int>&coins,intamount){\nsort(coins.rbegin(),coins.rend());\nintcount=0,remaining=amount;\nfor(intcoin:coins){if(remaining<=0)break;count+=remaining/coin;remaining%=coin;}\nreturnremaining==0?count:-1;}分数背包问题

问题定义给定物品的重量和价值，背包容量有限，可选择物品的部分装入，目标是最大化背包内物品总价值。

贪心策略按物品单位重量价值（价值/重量）从高到低排序，优先装入单位价值最高的物品，直至背包装满。

算法步骤1.计算每个物品的单位价值；2.按单位价值降序排序；3.依次选取物品，能全装则全装，否则装剩余容量部分。

代码实现思路对物品按单位价值排序，遍历物品，累计总价值并减少背包容量，直至容量为0或物品遍历完毕。哈夫曼编码问题定义：数据压缩的需求哈夫曼编码是一种用于数据压缩的贪心算法，通过构造最优前缀码，将频率高的字符用较短编码表示，频率低的字符用较长编码表示，以实现数据压缩。贪心策略：合并频率最低节点每次选择频率最低的两个节点合并为新节点，新节点频率为两者之和。重复合并直到只剩一个根节点，形成哈夫曼树。编码生成：遍历哈夫曼树从根节点出发，左子树标记为"0"，右子树标记为"1"，遍历至叶子节点得到对应字符的编码。频率高的字符路径短，编码长度小。Python实现核心步骤1.使用优先队列（最小堆）存储字符及其频率；2.循环合并最小频率节点构建哈夫曼树；3.递归遍历树生成编码表。例如：频率字典{'a':5,'b':9,'c':12,'d':13,'e':16,'f':45}生成编码{'f':'0','c':'100','b':'101','e':'111','a':'1100','d':'1101'}。最小生成树

最小生成树的定义最小生成树是连通加权无向图中，包含所有顶点且边权之和最小的树结构，具有n个顶点和n-1条边，无环且连通。

贪心策略在最小生成树中的应用最小生成树问题可通过贪心算法求解，核心策略是每次选择权值最小的边，同时避免形成环，常见算法有Prim算法和Kruskal算法。

Prim算法核心思想从任意顶点开始，逐步添加与当前生成树相连的最小权值边，直至包含所有顶点，适用于稠密图，时间复杂度通常为O(n²)。

Kruskal算法核心思想将所有边按权值从小到大排序，依次选择不形成环的边加入生成树，使用并查集判断环，适用于稀疏图，时间复杂度为O(ElogE)。最短路径问题

问题定义在加权图中，从一个起始顶点到其他所有顶点的最短路径长度总和最小的路径。

贪心策略每次选择当前距离起始顶点最近且未被访问的顶点，更新其邻接顶点的距离。

Dijkstra算法通过优先队列（最小堆）实现，按距离递增顺序处理顶点，逐步确定最短路径。

适用场景适用于边权非负的有向图或无向图，如导航系统路径规划、网络路由优化。05经典例题解析：分糖果问题描述与分析问题场景定义明确问题的具体场景与约束条件，例如资源分配、时间调度、最优路径等，建立问题的基本模型。核心目标提取从问题中提炼出需要优化的核心目标，如最大化数量、最小化成本、最短路径等，明确求解方向。关键要素识别识别问题中的关键变量与限制条件，例如物品重量与价值、活动时间区间、硬币面额等，为策略设计提供依据。冲突与矛盾分析分析问题中存在的资源冲突或目标矛盾，例如有限资源与多需求的冲突，为贪心策略的制定提供切入点。明确问题目标确定问题需要达成的核心目标，例如找零问题中目标是使用最少硬币数量，活动选择问题中目标是选择最多不冲突活动。分析局部最优标准根据问题目标，确定每一步的"最优"判断标准，如找零问题选择最大面额硬币，活动选择问题选择最早结束活动。验证策略有效性通过简单案例验证策略能否导向全局最优，例如验证"先选结束早的活动"能否获得最大活动数量，避免局部最优陷阱。数据预处理对输入数据进行排序或转换，如按结束时间排序活动列表，按单位价值排序背包物品，为贪心选择提供有序基础。贪心策略制定算法思路详解问题拆解：划分局部决策步骤将复杂问题分解为多个连续的局部决策步骤，每个步骤对应一个子问题，通过解决子问题逐步构建全局解。策略制定：明确局部最优标准根据问题特性确定“最优”规则，如“选最小”“选最大”“选最早结束”等，这是贪心算法的核心。排序预处理：按策略规则排序多数贪心问题需先对数据排序，如活动选择问题按结束时间排序，分糖果问题对需求和糖果大小排序。迭代选择：逐步构建解决方案按贪心策略遍历数据，每步选择当前最优解加入结果集，直至问题解决或遍历结束，如零钱找零优先选大面额硬币。代码实现与解读分糖果问题代码实现

对孩子需求数组g和糖果数组s排序后，使用双指针遍历，优先用最小糖果满足最小需求孩子。核心代码：sort(g.begin(),g.end());sort(s.begin(),s.end());循环比较s[cookie]>=g[child]，满足则child++，cookie始终++。摇摆数组代码实现

定义BEGIN、UP、DOWN三种状态，初始状态为BEGIN。遍历数组时根据相邻元素差更新状态，状态切换时增加摇摆序列长度。如从BEGIN到UP/DOWN，或UP到DOWN、DOWN到UP时max_length++。移除K个数字代码实现

使用栈存储结果，遍历字符串数字，当栈非空且当前数字小于栈顶元素且k>0时，弹出栈顶元素（k--），最后处理剩余k（从栈尾删除）。注意去除前导零，结果为空时返回"0"。06经典例题解析：摇摆数组问题定义明确问题的目标与约束条件，将实际问题抽象为可计算的模型，例如求最优解、最大/最小值等。核心需求提取从问题描述中提取关键要素，如输入数据、输出要求、限制条件等，确定问题的核心矛盾与解决方向。可行性判断分析问题是否具备贪心选择性质和最优子结构，判断贪心算法是否适用，避免盲目套用导致非最优解。案例场景分析以分糖果问题为例：已知孩子需求因子数组g和糖果大小数组s，每个孩子最多用1个糖果，求最多满足的孩子数量，需分析如何匹配孩子与糖果以实现最大化。问题描述与分析贪心策略制定问题特性分析判断问题是否具备贪心选择性质和最优子结构，这是制定有效贪心策略的前提。排序预处理多数贪心问题需先对数据按特定维度排序，如活动选择问题按结束时间排序，分糖果问题对需求和糖果大小排序。局部最优标准定义明确每一步的“最优”标准，例如找零问题选最大面额，活动选择选最早结束，摇摆数组保留连续增减的首尾元素。迭代选择与验证按贪心策略逐步选择，构建解决方案，同时验证每一步选择的可行性及是否能导向全局最优。算法思路详解

问题分析与拆解将原问题分解为若干连续的局部决策步骤，明确每一步的目标与约束条件，识别问题的核心矛盾与优化方向。

贪心策略制定确定"当前最优"的判断标准，如选择最小/最大元素、最早/最晚结束时间等，确保策略符合贪心选择性质。

数据预处理对输入数据进行排序、过滤或转换，如按特定维度排序（升序/降序），为贪心选择提供有序数据基础。

迭代选择与解构建按贪心策略逐步选择局部最优解，更新问题状态（如剩余资源、已选集合），直至满足终止条件（如资源耗尽或遍历完成）。

解的验证与调整检查构建的解是否满足问题约束，必要时对边缘情况（如剩余资源未耗尽）进行处理，确保解的完整性与正确性。代码实现与解读

排序预处理多数贪心问题需先对数据排序，如分糖果问题对孩子需求和糖果大小数组升序排序，活动选择问题按结束时间排序。

迭代选择逻辑按贪心策略逐步选择，如分糖果中用双指针遍历，满足条件则分配并移动指针；摇摆数组通过状态机切换统计最长子序列。

数据结构优化使用优先队列（如巧克力问题选最低价格）、栈（如移除K个数字维护递增序列）提升选择效率，降低时间复杂度。

边界条件处理需考虑特殊情况，如移除K个数字后k仍大于0时截取末尾；找零问题中硬币面额不足时返回-1，确保算法健壮性。07经典例题解析：移除K个数字问题场景构建以分糖果问题为例：已知孩子需求因子数组g和糖果大小数组s，当s[j]≥g[i]时可满足孩子，每个孩子最多用1个糖果，求最多能满足的孩子数量。核心矛盾提炼当一个糖果可满足多个孩子，或一个孩子可被多个糖果满足时，如何选择才能最大化满足数量？需解决"糖果分配优先级"问题。关键约束条件1.每个孩子只能被1个糖果满足；2.每个糖果只能使用1次；3.需通过局部最优选择实现全局最优解。问题抽象建模将问题转化为双数组匹配问题：对g和s排序后，通过双指针遍历，每次用最小可用糖果满足最小需求孩子，实现资源最优分配。问题描述与分析贪心策略制定

问题拆解：划分独立子问题将原问题分解为一系列连续的局部决策步骤，每个步骤对应一个子问题，通过解决子问题逐步构建全局解。

标准确立：明确局部最优准则根据问题特性确定“最优”标准，如选择最小/最大元素、最早/最晚结束时间等，这是贪心策略的核心。

排序预处理：优化选择效率多数贪心问题需先对数据按策略规则排序（如活动按结束时间排序、物品按单位价值排序），为迭代选择奠定基础。

迭代选择：逐步构建解决方案按贪心策略遍历候选集合，每步选择当前最优元素加入解集合，直至满足问题约束或遍历完成。算法思路详解

问题拆解：分解为连续局部决策步骤将复杂问题拆分成多个连续的局部决策步骤，每个步骤对应一个子问题，通过解决子问题逐步构建整体解决方案。

确定贪心策略：明确“当前最优”标准根据问题特点明确每一步的“最优标准”，例如“选最小”“选最大”“选最早结束”等，这是贪心算法的核心。

排序预处理：按策略规则排序数据多数贪心问题需先对数据按策略对应的规则排序