1.贪心算法简介1.1贪心算法的定义贪心算法（GreedyAlgorithm）：一种在每次决策时，总是采取在当前状态下的最好选择，从而希望导致结果是最好或最优的算法。贪心算法是一种改进的「分步解决算法」，其核心思想是：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好/最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好/最优结果（全局最优解）」。换句话说，贪心算法不从整体最优上加以考虑，而是一步一步进行，每一步只以当前情况为基础，根据某个优化测度做出局部最优选择，从而省去了为找到最优解要穷举所有可能所必须耗费的大量时间。1

一、动态规划（DynamicProgramming）        术语“动态规划”最初是在1940年代由 理查德·贝尔曼 用来描述解决问题的过程，在这个过程中，人们需要一个接一个地找到最佳决策。到1953年，他将其精炼成为现代的含义，特别是指将较小的决策问题嵌套在较大的决策中，并且该领域随后被电气电子工程师学会认可为系统分析和工程学主题。贝尔曼的贡献以贝尔曼方程的名义被铭记，它是动态规划的核心结果，它以递归(计算机科学)形式重申了优化问题。        动态规划是一种解决多阶段决策问题的优化方法。通过将问题分解为一系列重叠的子问题，并使用子问题的解来构建更大问题的解。动态规划通常用于优化递

🚀点击这里可直接跳转到本专栏，可查阅顶置最新的华为OD机试宝典~本专栏所有题目均包含优质解题思路，高质量解题代码(Java&Python&C++&JS分别实现)，详细代码讲解，助你深入学习，深度掌握！文章目录一.题目二.解题思路三.题解代码Python题解代码JAVA题解代码C/C++题解代码JS题解代码四.代码讲解(Java&Python&C++&JS分别讲解)寄语

点击此处查看原题​​​​​​​*思路：首先要求0011尽可能的多，所以尽可能多的多配对，配对只在i,i+1之间发生，所以只需要关注str[i]和str[i+1]即可，如果str[i]==str[i+1]，那么一定配对，res++,否则说明只有str[i]==0&&str[i+1]==1或者str[i]==1&&str[i+1]==0两种情况，对于这种情况直接跳过，如果str[i]或者str[i+1]中的某一个是？的话，那么一定可以和下一个字符匹配，所以res++,如果是？？,那么随便是11和00都可以，不必担心后面的数，假如??00 =2,??01=1,??11=2,??10=1，说明当前的s

29.两数相除给你两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和取余运算。整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345将被截断为8，-2.7335将被截断至-2。返回被除数dividend除以除数divisor得到的商。注意：假设我们的环境只能存储32位有符号整数，其数值范围是[−231,231−1][−2^{31},2^{31}−1][−231,231−1]。本题中，如果商严格大于231−12^{31}−1231−1，则返回231−12^{31}−1231−1；如果商严格小于−231-2^{31}−231，则返回−

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言贪心算法的定义：贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。解题的一般步骤是：1.建立数学模型来描述问题；2.把求解的问题分成若干个子问题；3.对每一子问题求解，得到子问题的局部最优解；4.把子问题的局部最优解合成原来问题的一个解。如果大家比较了解动态规划，就会发现它们之间的相似之处。最

系列文章目录高级算法设计与分析（一）--算法引论高级算法设计与分析（二）--递归与分治策略高级算法设计与分析（三）--动态规划高级算法设计与分析（四）--贪心算法高级算法设计与分析（五）--回溯法高级算法设计与分析（六）--分支限界法高级算法设计与分析（七）--概率算法和NP完全性理论高级算法设计与分析（八）--总结目录系列文章目录前言一、贪心算法的基本思想二、活动安排问题三、贪心算法的基本要素四、哈夫曼编码五、单源最短路径-Dijkstra算法六、最小生成树1、基础概念与问题2、prim算法（普里姆算法）3、kruskai算法（克鲁斯卡尔算法）习题前言tips：这里只是总结，不是教程哈。鉴于

一.引言本文将通过两个问题和两道例题带你入门贪心算法。贪心算法（GreedyAlgorithm）是一种在每一步选择中都采取在当前状态下最优（最好或最有利）的选择，从而希望导致全局最优解的算法。贪心算法不保证找到全局最优解，但通常可以快速找到一个接近最优解的解。二.背包问题和找零问题1.背包问题即为给你一个背包的容量，告诉你每个物品的价值和重量，找到最大价值的物品代码实现：解析：这不是0/1背包问题，而是分数背包问题（可以拿一部分物品），我们先对goods的单价排序，然后创建一个列表来记录每个物品要拿多少，然后遍历goods，如果背包容量大于物品重量，则记为1，背包容量减少，如果不够则记录分数，

什么时候使用贪婪算法?–贪心选择特性:全局的最优解可以通过局部的最优（贪婪）选择得到.•动态规划需要检查子问题的解。–最优子结构:问题的最优解包含了其子问题的最优解.•例如,如果A是S的最优解,那么A'=A-{1}是的最优解.•贪心算法(试探)并不能总是得到最优解.•谈论算法和动态规划(DP)对比–相同:最优子结构–差别:贪婪选择特性–如果贪婪算法不是最优的，可以使用DP。活动选择问题给定一个集合S={1,2,…,n}n个计划的活动,对每个活动，开始时间为 结束时间为,选择出相互兼容的活动最大集合.–如果被选中,活动 在半开放的区间中进行.–活动 和兼容如果 和 不重叠问题分析基本思想 对应伪

文章目录一、虚拟汽车加油问题1.1问题描述1.2思路分析1.3代码编写二、最优分解问题2.1问题描述2.2思路分析2.3代码编写一、虚拟汽车加油问题1.1问题描述 一辆虚拟汽车加满油后可行驶nnnkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少，计算最少加油次数。数据输入：第一行有两个整数n和k，表示汽车加满油后可行驶nkm,且路途中有k个加油站。接下来的一行中有k+1个整数，表示第k个加油站与k-1个加油站之间的距离。第0个加油站表示处出发地，汽车已加满油，第k+1个加油站便是目的地。数据输出：将计算的最少加油次数输出，如果无法到达目的地，则输出“N