- 综合排序
- 最热优先
- 最新优先
- 来自专栏C/C＋＋、数据结构、算法
贪心算法总结（3）
/要获取一个数的数位关系的时候 一般有两个技巧，第一个是变成字符串 第二个就是/10 %10 int monotoneIncreasingDigits(int n) { //根据贪心策略 %2) return hash[n]=1+min(dfs(n-1),dfs(n+1)); else return hash[n]=dfs(n/2)+1; } }; 解法2：贪心 while(n>1) { if(n%2==0) n/=2,++ret; else { if(n==3) class Solution { public: int maxSumDivThree(vector<int>& nums) { // 正难则反 //sum%3= =0 //sum%3==1 x1 或者y1y2 //sum%3==2 x1x2或者y1 const int INF=0x3f3f3f3f
26910编辑于 2024-08-11 - 来自专栏每天学Java
贪心算法如何贪心
在前面学习最短路径和最小生成树的时候，我们发现Dijkstra算法，Prim算法，Kruskal算法都是属于典型的贪心算法应用。 这篇文章就是对于贪心算法的入门介绍 贪心算法 贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。 问题所具有的这个性质是该问题可用动态 规划算法或贪心算法求解的一个关键特征。 我们通过下面两个例题来看下什么时候选用贪心算法求解。 只要能满足贪心算法的两个性质： 贪心选择性质和最优子结构性质，贪心算法就可以出色地求出问题的整体最优解。即使某些问题，贪心算法不能求得整体的最优解，贪心算法 也能求出大概的整体最优解。
1.6K10发布于 2020-06-01 - 来自专栏C++
【算法】贪心
4、贪心算法： 数组中两个字符串的最小距离 #include <iostream> using namespace std; int main() { int n; cin >> n; string str1, str2, str3; cin >> str1 >> str2; int l = -1, r = -1, ret = n; for (int i = 0; i < n; i++) { cin >> str3; if (str1 == str3) l = i; if (str2 == str3 = -1 || r == -1) cout << -1; else cout << ret; return 0; } 活动选择问题 最小生成树（Prim、Kruskal算法
26700编辑于 2025-03-14 - 来自专栏半生瓜のblog
【算法】贪心算法
贪心算法 概念解释 贪婪算法(贪心算法)是指在对问题求解的时候，每一步选择都采用最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。 贪心算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。 贪心算法并没有固定的解发框架，算法的关键是贪心策略的选择，根据不用问题选择不同的策略。 解题思路： 用贪心算法的思想，每一步都用能用的最大纸币即可。 会提示找不开，这种情况下我们使用贪心算法得到的答案就不是最优解，因为我们一直在尝试用最大的纸币来尽可能的使用最少的张数来解决问题。这就不是最优的。 贪心算法没有固定的框架，关键是看你怎么选择。 这种情况就需要调整策略，甚至，就不适用贪心算法。 贪心算法是尽力找到近似的最优解，注重的是速度，不是精准度，并不是说一定能找到合适的解,或是一定能找到解 。 对应问题根据情况不同选择合适的算法解决。
63630编辑于 2023-05-13 - 来自专栏周小末天天开心
【趣学算法】Day3 贪心算法——背包问题
（3）使用贪心算法求解问题 算法分析 ---- 题目描述 有n种物品，每种物品只有一个，第i种物品的重量为 wi，价值为 vi，背包的容量为 w，物品可以分割。 因此，我们应采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。 算法设计 （1）确定合适的数据结构并初始化。 （2）根据贪心策略，按照单位重量价值从大到小选取物品，直到达到背包容量。如果在装入第 i 个物品时超出背包容量，则取该物品的一部分装入背包。 完美图解 物品的价值和重量如表2-3所示。 物品清单 物品 i3 1 2 3 4 5 6 7 8 9 10 重量 w[i] 4 2 9 5 5 8 5 4 5 5 价值 v[i] 3 8 18 6 8 20 5 6 7 15 （1）贪心策略是每次选单位重量价值 （3）构造最优解 算法详解 （1）确定合适的数据结构。
1.4K30编辑于 2022-11-12 - 来自专栏_春华秋实
贪心算法
贪心算法：分阶段的工作，在每个阶段做出当前最好的选择，从而希望得到结果是最好或最优的算法。 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。 1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct{ 4 int time; 5 int weight; 6 扫描下一个：从右断点覆盖，直到覆盖两个点；（从左端扫描，右端覆盖） 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[15]; 4 int n; 5 int abs(int x){ return ( 56 */ 最近做了一些贪心算法的题，感觉贪心算法主要是根据问题的要求想出贪心策略，上面提到了没有涉及到什么数据结构和高精度的问题。所以用到最多的就是排序。
89630发布于 2019-02-22 - 来自专栏kwai
算法(四) 贪心
贪心算法 例题 1，最大子序和 来自LeetCode 53 解法 1，贪心 根据题意我们可以发现这样一个贪心思想：当前面子序列和小于0时，不如从自身重新开始计算。 3，分治法 见分治法文章。
50670编辑于 2022-01-10 - 来自专栏用户2442861的专栏
贪心算法
http://blog.csdn.net/xywlpo/article/details/6439048 贪心算法的设计思想 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择 如果只有面值分别为1，5和11单位的硬币，而希望找回总额为15单位的硬币，按贪婪算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。 （2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。 （3）解决函数solution：检查解集合S是否构成问题的完整解。 但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 这是贪心算法可行的第一个基本要素。 贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
2K20发布于 2018-09-14 - 来自专栏常用算法模板
算法基础-贪心
数据范围 1\le N\le 10^5,−10^9\le a_i\le b_i\le 10^9 输入样例： 3 -1 1 2 4 3 5 输出样例： 2 题解 时间复杂度 O(nlogn) 证明: 证明 typedef long long LL; typedef pair<int, int> PII; typedef unsigned long long ULL; const int Inf = 0x3f3f3f3f
81820编辑于 2022-10-31 贪心算法.
序幕 贪心算法（Greedy Algorithm）是一种在求解问题时采取逐步构建解决方案的策略，每一步都选择当前状态下局部最优的解，期望通过局部最优解能够得到全局最优解。 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 我们需要是，各种峰值，当数字处于上升阶段时，若不止一个数字，就要将其去掉 小结 其实，简单的说，贪心算法就像是 从局部，找到一个规律，并且这个规律适用于全局 一但明白这点，无论难度多大的题，我们都会怀着
25610编辑于 2025-10-22【算法篇】贪心算法
贪心算法 贪心算法，是一种在每一步选择中都采取当前状态下的最优策略，期望得到全局最优解的算法策略。也就是说，通过局部最优解，期望得到全局最优解。 贪心算法一般按如下步骤执行： 1，问题分解： 将原问题转化为一系列子问题。 2，贪心选择：对每个子问题求解的时候，都选择当前看起来“最优的”解法。 3，合并解：累计局部最优解形成全局解。 这里假设k=46，用 贪心算法的思想，每一步尽可能使用面值最大的纸币即可。 贪心算法实际应用 一，零钱找回问题 假设1元，5元，10元，20元，50元，100元的纸币分别有 c0,c1,c2,c3,c4,c5张 。现在用这些钱来找回k元，求最少使用的张数。 用贪心算法的思想，每一步找钱尽可能使用面值大的。
62610编辑于 2025-12-30- 来自专栏深度学习计算机视觉
贪心算法+回溯算法
贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择，不考虑整体，只考虑局部最优，所以它不一定能得到最优解； 动态规划则是每个步骤都要进行一次选择，但选择通常要依赖子问题的解 所以一般选自自底向上自带备忘的机制，所以一定是最优解； 最优子结构的概念 如果一个问题的解包含其子问题的最优解，则称该问题具有最优子结构，也就是求解大问题的解，是通过求解小问题取解决 如果理解了最优子结构，则会发现贪心算法和动态规划都利用了最优子结构的性质 实现该算法的过程 从问题的某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 典型的可用贪心来解的问题有 最小生成树、分数背包问题（ 所以先选择B，再选择A 再从C中选择5 这时价值肯定最大 但贪心算法一开始就说了，并不保证最优解，所以有时会配合随机算法（算法导论第三版第五章有讲）使用 一般来说贪心算法的代码比动态规划简单的多 利用回溯法解决该类问题步骤 1、针对所给问题，定义问题的解空间； 2、确定易于搜索的解空间结构； 3、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
1.8K91发布于 2018-04-24 - 来自专栏C++/Linux
【算法专题】贪心算法
贪心算法 贪心算法介绍 什么是贪心算法呢？ 首先，我们需要知道贪心策略，即解决问题的策略，将局部最优转变为全局最优； 把解决问题的过程分为若干步； 解决每一步的时候，都选择当前看起来"最优的"解法； "希望"得到全局最优解 贪心算法的特点： 提出贪心策略 思路：贪心算法，其中这道题我们在动态规划专题也做过。 最长递增子序列(贪心算法) 题目链接 -> Leetcode -300.最长递增子序列 Leetcode -300.最长递增子序列 题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 买卖股票的最佳时机Ⅱ(贪心算法) 题目链接 -> Leetcode -122.买卖股票的最佳时机Ⅱ Leetcode -122.买卖股票的最佳时机Ⅱ 题目：给你一个整数数组 prices ，其中 prices
59210编辑于 2024-03-01 - 来自专栏开心的学习之路
贪心算法
贪心算法的基本思想： ------求解最优化问题的算法包含一系列步骤 ------每一部都有一组选择 ------做出当前看来最好的选择 ------希望通过做出局部优化选择达到全局优化选择 - -----贪心算法不一定总产生优化解 ------贪心算法是否产生优化解，需要严格证明 贪心算法产生优化解的条件 ------贪心选择性：若一个优化问题的全局优化解可以通过局部优化选择得到，则该问题成为具有贪心选择性 ------优化子结构 与动态规划方法的比较 ------动态规划方法可用的条件：（1）优化子结构（2）子问题重叠性（3）子问题空间小 ------贪心法可用的条件：（1）优化子结构（2）贪心选择性 这是一种典型的贪心算法，它只顾眼前，但能得到最优解。 （2）部分背包问题。有n个物体，第i个物体的重量为wi，价值为vi，在总重量不超过C的情况下让总价值尽量高。 一种直观的贪心策略是：优先拿“价值除以重量的值”最大的，直到重量和正好为C。
1.3K20发布于 2019-02-14 - 来自专栏linux驱动个人学习
贪心算法
贪婪算法 贪心算法（Greedy Algorithm) 简介贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择 这里需要明确的几个点：1.货币只有 25 分、10 分、5 分和 1 分四种硬币；2.找给客户 41 分钱的硬币；3.硬币最少化思考，能使用我们今天学到的贪婪算法吗？怎么做？ index = i; } } } return index; } 有了物品，有了方法，下面就是将两者结合起来的贪心算法 按照贪心算法的三个步骤：1.41分，局部最优化原则，先找给顾客25分；2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；3.最终，找给顾客一个25分，一个10分，一个5分，一个1分 ^_^;总结：贪心算法的优缺点优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解
1.4K11发布于 2020-02-12 - 来自专栏编程学习之路
【算法】之贪心算法
欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~ 目录 贪心算法 算法知识点 解题步骤 算法题目来源 算法题目描述 做题思路 代码 运行结果 读书笔记 ---- 贪心算法 算法知识点 贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。 贪心算法一般用来解决求最大或最小解。 解题步骤 1.分解：将原问题分解为若干个相互独立的阶段 2.解决：在每个相互独立的阶段进行贪心选择，求出局部最优解 3.合并：将各个阶段的解合并为原问题的解 算法题目来源 860. 贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。
92230编辑于 2022-11-20 - 来自专栏WHYBIGDATA公众号同步文章
贪心算法(Java)
贪心算法(Java) 0、写在前面 1、贪心算法的基本要素 1.1 贪心选择性质 1.2 最优子结构性质 1.3 贪心算法与动态规划算法的差异 2、贪心算法的特点 3、贪心法的正确性证明 4、活动安排问题 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 1.3 贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。 贪心法必须进行正确性证明 贪心法的优势：算法简单，时间和空间复杂性低 3、贪心法的正确性证明 数学归纳法 叙述一个描述算法正确性的命题P(n)，n为算法步数或者问题规模 归纳基础：P(1) 或 P(n0 4.2 贪心法的设计思想 4.3 两个反例 策略1：S={1,2,3}，s1=0, f1=20, s2=2, f2=5, s3=8, f3=15 策略2：S={1,2,3}，s1=0, f1 =8, s2=7, f2=9, s3=8, f3=15 5、代码 活动安排 Note：各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 public static int
95510编辑于 2023-01-31 - 来自专栏爱编码
经典算法之贪心算法
什么是贪心算法？ 贪心算法，又称贪婪算法(Greedy Algorithm)，是指在对问题求解时，总是做出在当前看来是最好的选择。 贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。 如果确定可以使用贪心算法，那一定要选择合适的贪心策略； 贪心算法的几个例子 1. 比如1元，2元，3元，4元，8元，15元的纸币，用来支付K元，至少多少张纸币？ 经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。 比如1元10张，20元5张，50元1张，那用来支付60元，按照上面的算法，至少需要1张50元，10张1元，而实际上使用3张20元的即可； （3）所以贪心算法是一种在某种范围内，局部最优的算法。
2.1K30发布于 2019-11-08 - 来自专栏zxctscl个人专栏
【算法】贪心算法练习一
贪心算法的介绍 一、贪心策略：解决问题的策略，局部最优->全局最优 把解决问题的过程分为若干步； 解决每一步的时候，都选择当前看起来“最优的”解法； 希望得到全局最优。 二、贪心策略的正确性 因为有可能“贪心策略”是一个错误的方法 正确的贪心策略，是需要证明的 常见的证明方法就是在数学中见过的所有证明方法。 三、学习贪心算法的方向 遇到不会的贪心题，很正常，把心态放平。 前期学习的时候，把重点放在贪心的策略上，把这个策略当做经验吸收。 如何证明贪心策略是正确的 2. 860. } } return true; } }; 3. 2208. 二、算法原理 每次挑选当前数组中，最大的那个数，然后减半，最大的数减半，才有可能最快减到数组和减少到至少一半。
28510编辑于 2024-04-10 - 来自专栏编程学习
算法训练之贪心
前置知识 在真正开始贪心算法题目练习之前，我们首先要了解什么是贪心算法？贪心算法有什么特点？ 什么是贪心算法? "解法;（鼠目寸光） 3." ~ 从左上角开始，我们每一步都按当前位置的最优选择（局部最优解）进行，但是不难发现结果是错误的~所以我们是"希望"得到全局最优解，但是结果不一定近人意，我们就需要更改我们的贪心策略~ 贪心算法的特点 结合前面的例子，我们可以发现贪心算法有下面的特点： 一、贪心策略的提出 1.贪心策略的提出是没有标准以及模板的 2.可能每一道题的贪心策略都是不同的 二、贪心策略的正确性 /性质： 相同的分析可以得到B、C、D满足B<=1,C<=1,D<=4 我们继续来看，假设贪心算法得到的面值为20、10、5、1的张数分别为a、b、c、d~ 既然最优解是最少的张数的话，
33410编辑于 2025-04-15
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号