网站开发人员的工作,北京官方seo搜索引擎优化推荐,网站建设谈判技巧,好的设计logo网站【25届秋招备战C】算法篇-贪心算法 一、简介二、解题思路三、应用场景四、模板函数五、参考 一、简介
一种在每次决策时#xff0c;总是采取在当前状态下的最好选择#xff0c;从而希望导致结果是最好或最优的算法。通常用于解决一些最优化问题#xff0c;如找零问题、霍夫… 【25届秋招备战C】算法篇-贪心算法 一、简介二、解题思路三、应用场景四、模板函数五、参考 一、简介
一种在每次决策时总是采取在当前状态下的最好选择从而希望导致结果是最好或最优的算法。通常用于解决一些最优化问题如找零问题、霍夫曼编码、最小生成树问题等。在每一步都做出当前看起来最好的选择不考虑这个选择对后续步骤的影响。这种策略有时能够导致全局最优解但并不是所有问题都适用。在某些问题中贪心算法可能只能得到局部最优解而不是全局最优解。 如何验证可不可以用贪心算法呢 最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
二、解题思路
将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解
三、应用场景
分糖果问题 场景描述有m个糖果要分给n个孩子每个糖果的大小不同每个孩子对糖果的需求也不同。目标是尽可能满足最多数量孩子的需求。 解决方法给所有孩子的需求排个序从需求最小的孩子开始用刚好能满足他的糖果来分给他以此来分完所有的糖果。找零钱问题 场景描述有不同面额的纸币需要找零K元目标是使用最少的纸币数量。 解决方法先用面值最大的纸币去付钱当再加一张就会超过K时就更换小面额的直至正好为K元。区间覆盖问题 场景描述给定n个区间需要从中选出尽可能多的不相交的区间。 解决方法每次选择左端点大于等于已覆盖区间右边端点的区间且该区间右端点尽可能小的以保证未覆盖区间尽可能大从而可以塞进去尽可能多的区间。图的最小生成树 场景描述在一个加权无向图中需要找到一个包含所有顶点的无环子图使得子图的总权重最小。 解决方法使用贪心策略如Kruskal算法或Prim算法逐步构建最小生成树。哈夫曼编码 场景描述需要为一组字符创建一个变长编码使得编码后的字符串长度尽可能短。 解决方法构建一棵哈夫曼树根据字符出现的概率分配编码。活动安排问题 场景描述有一系列活动每个活动有开始时间和结束时间目标是选择最大的互不冲突的活动集合。 解决方法按照结束时间对活动进行排序然后贪心地选择结束时间最早的活动并排除与其冲突的活动。
四、模板函数
没得模板很难确定
五、参考
代码随想录 贪心算法-爱学习的饲养员 算法通关手册
