- 综合排序
- 最热优先
- 最新优先
- 来自专栏后台技术底层理解
贪心思想
在学习数据结构的时候，我们已经见过了贪心思想在Prim和Kruskal中的完美应用，贪心思想因为其的简洁在算法中经常会被用到，有的时候在生活中，我们也会无意中使用到l贪心算法。 那么什么是贪心思想？ 贪心 贪心算法总是作出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 其他的情况就需要进行证明，证明的最好办法就是将最小子问题进行一步步的合并，直到最后还原为最后的原问题，若所得到的解是总体最优的则可以使用贪心思想，否则不可以。 比如上面的问题，我们的走一步的最优解为1，3，然后我们判断一次走两步的最优解是否任然为1,3这个路径，答案显然不是，变为 1,2,100这个路径，所以显然不能使用贪心思想。 用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。
56320发布于 2020-08-04 - 来自专栏苦逼的码农
初识贪心思想
来源：小小算法 作者：小小算法 初识贪心思想 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪心算法的本质就是，每次只顾眼前利益，并且到最后能获得最大利益。 这里没有什么套路，只要它能通过局部能得到全局最优，那就可以使用贪心思想的步骤去解决了。 接下来通过我从 leetcode 精选的一个贪心题来体验一下贪心思想和这类题的解题步骤。 ---- 首先判断能否用贪心算法来解决 再次强调，一个题能不能用贪心思想来解决取决于它能不能通过局部最优得到全局最优。 前期多使用纯粹的贪心思想解决题目会对我们理解贪心很有帮助。 这里我还找了一个可以使用纯粹贪心思想解决的题，大家有空可以去做做： 135. 分发糖果[1] 你知道吗？ Dijkstra 最短路径算法也使用了贪心思想，贪心思想还经常和二分、前缀和一起使用哦。加油吧。
90510发布于 2019-11-22 - 来自专栏第一专栏
最优合并问题------贪心思想
最优合并问题 Description 给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。 为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。 对于给定的k个待合并序列，计算最多比较次数和最少比较次数合并方案。
63930编辑于 2023-05-25 - 来自专栏第一专栏
骨牌铺方格------贪心思想
骨牌铺方格 Description 在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数. 例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
31430编辑于 2023-05-25 - 来自专栏第一专栏
汽车加油问题------贪心思想
汽车加油问题 Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置，计算最少加油次数。 Input 输入数据的第一行有2 个正整数n和k（n≤5000，k≤1000），表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 Output 将计算出的最少加油次数输出。如果无法到达目的地，则输出“No Solution!”。 Sample Input 7 7 1 2 3 4 5 1 6 6 Output 4
45430编辑于 2023-05-25 - 来自专栏学习之路
【算法训练】：贪心（算法 & 题目训练）
特性 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的 能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质 1. 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 这是贪心算法可行的第一个基本要素。 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 两者之间的区别在于： 贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。
34210编辑于 2024-10-22 - 来自专栏TechBlog
贪心算法思想与练习
文章目录 股票买卖 II 货仓选址 糖果传递 雷达设备 贪心的核心思想：最优解，短视。 按照数据规模猜测贪心，一般在 10 ^ 5 是排序， 10 ^ 6 或 10 ^ 7 是O(n)的做法，扫描一边，1000左右是两重循环，100左右是三重循环。 贪心思路： 任何跨度大于一天的交易都可以拆分成跨度等于一天的交易（中间部分的买和卖相互抵消了）。所以最优解只需要聚焦在这跨度为1的交易上即可，那么基本思路就是如果后一天价格大于前一天，则交易一次。 4 思路： 题目可以绘图如下： 其中： 那么可以看到： 由上式，可以归纳出： c_{i}=c_{i+1}+\bar{a}-a_{i} 那么原目标函数可以化简为： 这样就转换成与上一题一样的思想了 贪心策略： 将所有区间按右端点从小到大排序； 依次考虑每个区间： 如果当前区间包含最后一个选择的点，则直接跳过； 如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点
78420编辑于 2023-03-24 - 来自专栏编程学习
算法训练之贪心
前置知识 在真正开始贪心算法题目练习之前，我们首先要了解什么是贪心算法？贪心算法有什么特点？ 什么是贪心算法? 结合前面的例子，我们可以发现贪心算法有下面的特点： 一、贪心策略的提出 1.贪心策略的提出是没有标准以及模板的 2.可能每一道题的贪心策略都是不同的 二、贪心策略的正确性 ，那么也就说明是正确的~ 因此，正确的贪心策略，我们是需要"证明的"，证明结果正确才代表贪心策略正确，证明贪心策略不正确，只需要举一个反例，那么这个时候就需要我们对贪心策略进行调整了~ 答案是第一种，我们不难发现5美元是有很大用处的，10美元可以找，20美元也可以找，结合我们的生活经验，我们应该尽可能的保留5美元~这里就体现了我们贪心思想，优先选择当前情况下的最优解，最终得到全局的最优解 return false; } else//20元需要找15元 { //贪心思想
28010编辑于 2025-04-15 - 来自专栏全栈程序员必看
hdu 4105 贪心思想「建议收藏」
淋漓尽致的贪心思想 波谷一定是一位数。波峰一位数不够大的时候加入到两位数就一定够大了的。 当在寻找波谷碰到零了就自然当成波谷。 当在寻找波峰时碰到零时，将前面的波谷加到前一个波峰上。 让当前的零做波谷，使得波谷的值尽量小，这就是本题最关键的贪心思想。一直想不到。 代码中：a表示前一个值，b表示当前考虑的值，tag为偶数时表示正在寻找波谷，奇数时在寻找波峰。 (b == 0) { while(data[i] == '0'){ i ++; if(i >= n) break; } //贪心思想
20740编辑于 2022-01-28 - 来自专栏学习之路
【算法题目训练】：贪心练习
一、前言 之前在这篇文章里 【算法/训练】：贪心（算法理论学习及实践） 讲了贪心的知识，以及对于其的练习，这里的话我们就纯练习题目了，也是对之前的文章的补充，以后有关于贪心算法的题目也基本会放到这篇博客里面的 样例输入 3 121 12 96 样例输出 9612121 贪心策略 我们不考虑整体的最大，先考虑局部的最大，假如有 A B 两个整数，要使 A B 组合起来最大的话，则需要判断一下 A B > 样例输入 179566 4 样例输出 15 贪心策略 局部：每次删除一个离最高位最近的逆序位数字，比如 1234321，其中 43 是离最高位最近的逆序位，删除 4 即可 整体：此时按照上面策略执行 n 样例输入 2 10 2 样例输出 3 贪心策略 局部：ans 表示最小操作次数，则 ans 更新策略如下： 情况一：若 a*k <= b，则 ans += 1 + b %k，b /= k 情况二 而是一个 数据映射 的问题，下面画个图理解一下： 那么现在雷达可以放的位置就在 [a, b] 这个区间里面 那么现在问题就变成了，有若干个区间，在每个区间里面至少放置一个雷达，求放置雷达的最少数量 贪心策略
32510编辑于 2025-02-12 - 来自专栏热爱C嘎嘎
算法训练：贪心与回溯
目录 1.手套（贪心算法） 2.字符串通配符（回溯算法） ---- 1.手套 题目描述： 在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。 这里一般采用贪心算法。我们来分析一下： 因为在拿手套的时候，是盲拿的，拿了多少不知道，拿的是右手还是左手的也不知道。
52320编辑于 2023-03-30 - 来自专栏机器学习炼丹之旅
贪心思想的一点理解
根据acm训练计划，我被分配给大一新同学讲贪心专题，顺便看了几道经典的贪心例题，果然很多以前的东西都豁然开朗了，也有了一些新的理解，故随意记录一下。 （摘自维基百科） 我的理解 贪心的思想并不难理解 ——— 将一个问题分解成多个容易解决的子问题，让每一个子问题都最优，那么合起来得到的最终结果就是最优的，这样只要求出每个子问题的解，那么整个问题的解就不难得到了 所以，贪心的最大难点就是如何证明贪心解就等于最优解，这也是贪心问题的上限很高的原因。 在用现有的导弹系统拦截时，我们用贪心的思想，使用现有的可拦截高度大于导弹高度的最小的导弹系统。这就是此题的贪心策略，再次说明策略好找，最优性难证啊。 由贪心策略可知，a是大于x的最小的数，故 x<a<b 所以，我们可以将蓝色序列的贪心位置和最优位置互换使得当前状态下贪心转变成最优，以此类推，每当贪心和最优策略出现不同时，用这种调整的方法将贪心策略变成最优策略
55110编辑于 2022-06-29 - 来自专栏第一专栏
B - 多元Huffman编码问题------贪心思想
B - 多元Huffman编码问题 Description 在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。 对于给定n堆石子,计算合并成一堆的最大总费用和最小总费用。
40920编辑于 2023-05-25 - 来自专栏vblog
PAT 1033 To Fill or Not to Fill (25分) 贪心思想
思路分析 核心思想：贪心算法（每次寻找局部最优，在最便宜的加油站加最多的油）。 贪心核心：怎么实现每次都做出局部最优的选择？
81520发布于 2020-07-14 - 来自专栏前端进阶-詹躲躲
【算法】分治思想、动态规划、回溯、贪心算法
我们来从归并排序理解分治思想，归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来。 上代码。 新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。 使用动态规划思想解题，首先要明确动态规划的三要素。 Greedy 最近某音很火的贪心土味情话 喂，不是吧。 回到算法中，贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。实际上，用贪心算法解决问题的思路，并不总能给出最优解。因为它在每一步的决策中，选择目前最优策略，不考虑全局是不是最优。 饼干满足胃口，更新满足的孩子数并移动指针 i++ j++ res++ 当饼干 j < 胃口 i 时，饼干不能满足胃口，需要换大的 j++ 关键点 将需求因子 g 和 s 分别从小到大进行排序，使用贪心思想配合双指针
1.1K20编辑于 2022-09-06 - 来自专栏C++信息学奥赛
杨校老师课题之备战C++竞赛训练专题--排序与思维提升(贪心思想)
有 N个人要参加围棋比赛，该比赛要进行 K 场对弈。每个人最多参加两场对弈，最少参加零场对弈。每个人都有一个与其他人不相同的等级（用一个正整数来表示）。在对弈中，等级高的人必须用黑色的棋子，等级低的人必须用白色的棋子。每个人最多只能用一次黑色的棋子和一次白色的棋子。为增加比赛的可观度，观众希望 K 场对弈中双方的等级差的总和最小。比如有 7 个选手，他们的等级分别是 30,17,26,41,19,38,18要进行 3 场比赛。最好的安排是选手 2 对选手 7，选手 7 对选手 5，选手 6 对选手 4。此时等级差的总和等于 (18−17)+(19−18)+(41−38)=5 达到最小。
14410编辑于 2026-04-01 - 来自专栏鳄鱼儿的技术分享
【贪心】算法思想，附两道道手撕题
贪心思想是一种解决问题的方法，它通过在每一步选择中都采取最好或者最优的选择，以期望最终结果也是最好或者最优的。 这种思想简单直接，但在某些问题上却能发挥出惊人的效果。 贪心思想的定义 贪心算法是一种在每一步选择中都采取局部最优解的算法，希望这些局部最优解最终能够累积成全局最优解。 然而，需要注意的是，贪心算法得到的结果并不总是最优的，有时候它只能提供近似最优解。 贪心思想的性质 最优子结构性质 最优子结构性质是贪心算法能够工作的基础。 它指的是一个问题的最优解包含其子问题的最优解。这意味着，通过解决子问题，我们可以构建出整个问题的最优解。 贪心思想的应用场景 贪心算法因其简单和高效，在多个领域都有广泛的应用。以下是一些典型的应用场景： 排序问题：选择排序和拓扑排序是贪心算法在排序问题中的典型应用。 优先队列：堆排序利用贪心思想，通过维护一个优先队列来实现高效的排序。 赫夫曼压缩编码：在数据压缩领域，贪心算法被用来构建最优的前缀编码。
46110编辑于 2024-12-29 - 来自专栏学习之路
【算法训练】：贪心（算法理论学习及实践）
贪心算法关键是：贪心策略的选择 特性 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解 能够用贪心算法求解的问题一般具有两个重要特性：贪心选择性质和最优子结构性质 1. 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 这是贪心算法可行的第一个基本要素。 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解 两者之间的区别在于： 贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。
70410编辑于 2025-06-02 - 来自专栏学习
【贪心算法】算法训练 ALGO-1003 礼物（CC++）
贪心算法（Greedy Algorithm) 概述： 贪心算法是一种在求解最优化问题时采取的一种常用算法策略。 贪心算法的基本思想是，每次选择当前情况下的局部最优解，并相信这个局部最优解能够导致全局最优解。贪心算法通过迭代的方式一步步地构建最优解，并不进行回溯，贪心主要就是每一步的最优必然导致最终结果的最优。 贪心算法的优点是简单、高效，时间复杂度通常较低。然而，贪心算法并不适用于所有问题，有些问题需要使用其他更复杂的算法来求解。在使用贪心算法时，需要仔细分析问题的特点并证明贪心策略的正确性。 算法训练 ALGO-1003 礼物 资源限制 内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s 问题描述 JiaoShou 在取石子时有很多限制条件，排列成一排我们可以理解为前缀和的思想处理，这样在计算石子的时候更快，在判断k为几时，我们的二分便可以倾巢而动了，用二分查找判断k，再利用一个check函数判断是否符合题意即可。
35610编辑于 2024-09-23 - 来自专栏每天学Java
贪心算法如何贪心
这篇文章就是对于贪心算法的入门介绍 贪心算法 贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 问题所具有的这个性质是该问题可用动态 规划算法或贪心算法求解的一个关键特征。 我们通过下面两个例题来看下什么时候选用贪心算法求解。 我们想一下为什么不能使用贪心算法，那是因为我们无法确定贪心策略，限制贪心策略的原因是ABC不能拆分， 不能拆分，就有了上面三种可能，但是如果可以拆分，那么策略三是可行的，先卖单价最贵的，但是如果单价相同那么得到的结果不是唯一的 只要能满足贪心算法的两个性质： 贪心选择性质和最优子结构性质，贪心算法就可以出色地求出问题的整体最优解。即使某些问题，贪心算法不能求得整体的最优解，贪心算法 也能求出大概的整体最优解。
1.4K10发布于 2020-06-01
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号