展开

关键词

算法贪心策略到动态规划

本文先介绍下贪心算法的缺点进而引出动态规划以及动态规划的解题中间的详细流程。 题目来源于 LeetCode 的第 206 题,难度为:中等。目前的通过率是43.6%。    1.贪心策略 ◼ 贪心策略:每一次都优先选择面值最大的硬币 选择 25 分的硬币,剩 16 分 选择10分的硬币,剩6分 选择5分的硬币,剩1分 选择 1 分的硬币 最终的解是共 4 枚硬币:25 分 ,通常作为其他算法的辅助算法来使用 ◼ 缺点:鼠目寸光,不从整体上考虑其他可能,每次采取局部最优解,不会再回溯,因此很少情况会得到最优解 ---- 2. 那么 dp(41-1) = dp(40) 表示凑够40需要的最少硬币数量。 那么 dp(41-5) = dp(36) 表示凑够36需要的最少硬币数量。 那么 dp(41-10) = dp(31) 表示凑够31需要的最少硬币数量。 那么 dp(41-20) = dp(21) 表示凑够21需要的最少硬币数量。

4910

贪心算法如何贪心

在前面学习最短路径和最小生成树的时候,我们发现Dijkstra算法,Prim算法,Kruskal算法都是属于典型的贪心算法应用。 这篇文章就是对于贪心算法的入门介绍 贪心算法 贪心算法(又称贪婪算法)是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 问题所具有的这个性质是该问题可用动态 规划算法贪心算法求解的一个关键特征。 我们通过下面两个例题来看下什么时候选用贪心算法求解。 只要能满足贪心算法的两个性质: 贪心选择性质和最优子结构性质,贪心算法就可以出色地求出问题的整体最优解。即使某些问题,贪心算法不能求得整体的最优解,贪心算法 也能求出大概的整体最优解。

47610
  • 广告
    关闭

    腾讯云精选爆品盛惠抢购

    腾讯云精选爆款云服务器限时体验20元起,还有更多热门云产品满足您的上云需求

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    贪心算法

    贪心算法:分阶段的工作,在每个阶段做出当前最好的选择,从而希望得到结果是最好或最优的算法贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。 任务调度问题(简单) 这是一个经典简单的贪心问题,只是题目有点长需要认真读。解决这个问题,重点要想好贪心的策略: 阶段性:每个时间表选择哪一个任务。 贪心策略:根据“误时惩罚”对任务进行排序,优先排惩罚大的任务,如果这个时间点已经被占了,依次向前找,判断任务是否能安排? 阶段性:每个区间选择那两个点 贪心策略:   对于所有的区间按右端点从小到大排序。(根据右端点排序)   从第一个区间开始扫描是否覆盖了两个点? 56 */ 最近做了一些贪心算法的题,感觉贪心算法主要是根据问题的要求想出贪心策略,上面提到了没有涉及到什么数据结构和高精度的问题。所以用到最多的就是排序。

    32230

    算法(四) 贪心

    贪心算法 例题 1,最大子序和 来自LeetCode 53 解法 1,贪心 根据题意我们可以发现这样一个贪心思想:当前面子序列和小于0时,不如从自身重新开始计算。

    9570

    贪心算法

    http://blog.csdn.net/xywlpo/article/details/6439048 贪心算法的设计思想          贪心算法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择 售货员希望用数目最少硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数,每次加入一个硬币。 如果只有面值分别为1,5和11单位的硬币,而希望找回总额为15单位的硬币,按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解答应是3个5单位面值的硬币。 但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质和最优子结构性质。 这是贪心算法可行的第一个基本要素。 贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。

    90020

    js算法初窥05(算法模式02-动态规划与贪心算法

    一、最少硬币找零问题 最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数,以及可用的硬币面额以及对应的数量,找出有多少种找零的方法。 最少硬币找零问题则是要找出其中所需最少数量的硬币。比如我们有1,5,10,25面额的硬币,如果要找36面额的钱,要如何找零呢?答案是一个25,一个10,一个1。这就是答案。 ,那么我们再来看看如何用贪心算法求解最少硬币找零的问题。 贪心算法从我们的硬币中最大的开始拿,直到拿不了了再去拿下一个,直到返回最终结果。那么我们看看两种解决方法有什么不通过。 我们后面会用贪心算法来解决分数背包问题。

    56830

    【DP、BFS】322. Coin Change

    Partition Equal Subset Sum 这道题那样,硬币从大到小排序,然后使用贪心算法来求解。 硬币对应完全背包问题中的物品重量,amount 对应背包容量,最少硬币数对应背包最大价值。 因此,我们只需要创建一个大小为 dp[amount+1] 的数组,dp[j] 表示兑换 j 块钱所需要的最少硬币数。 而之前写过这样的题目的做法:从M走到N最少步数。 对于这道题目,硬币种类数对应不同的走法,最少硬币数对应最少步数。因此,我们可以使用 BFS 方法求解。 注意:这道题和 从M走到N最少步数 的区别在于,找硬币问题的 amount 不一定可达。

    35130

    javascript经典算法之最小硬币找零问题

    正文 笔者抽空总结了几个比较经典且实用的算法, 最少硬币找零问题 是本文介绍的第一道算法题: 问题:给出要找零的钱数amount以及可用的硬币面额c1, c2, c3, ..., 求所需的最少硬币个数。 贪心算法 接下来笔者具体介绍这两种算法的思路和实现代码. 1. 动态规划法 动态规划的思想是把一个复杂问题分解为多个子问题,通过解决一个个子问题,再把子问题合并比较,从而解决复杂问题的思想。 当我们使用动态规划来解决该问题时,我们可以将其分解成几个子方案,最终通过条件判断最优方案,具体实现代码如下: // 硬币找零算法 function MinCoinChange(coins) { let 贪心算法 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。 其思想非常简单,我们直接上代码: // 最少硬币找零 - 贪心算法 function MinCoinChange1(coins) { return function(amount) { let

    72920

    贪心算法

    贪心算法的基本思想: ------求解最优化问题的算法包含一系列步骤 ------每一部都有一组选择 ------做出当前看来最好的选择 ------希望通过做出局部优化选择达到全局优化选择 - -----贪心算法不一定总产生优化解 ------贪心算法是否产生优化解,需要严格证明 贪心算法产生优化解的条件 ------贪心选择性:若一个优化问题的全局优化解可以通过局部优化选择得到,则该问题成为具有贪心选择性 ------优化子结构 与动态规划方法的比较 ------动态规划方法可用的条件:(1)优化子结构(2)子问题重叠性(3)子问题空间小 ------贪心法可用的条件:(1)优化子结构(2)贪心选择性 这是一种典型的贪心算法,它只顾眼前,但能得到最优解。 (2)部分背包问题。有n个物体,第i个物体的重量为wi,价值为vi,在总重量不超过C的情况下让总价值尽量高。 一种直观的贪心策略是:优先拿“价值除以重量的值”最大的,直到重量和正好为C。

    67920

    贪心算法

    贪婪算法 贪心算法(Greedy Algorithm) 简介贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择 事例一:找零钱问题假设你开了间小店,不能电子支付,钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币,如果你是售货员且要找给客户 41 分钱的硬币,如何安排才能找给客人的钱既正确且硬币的个数又最少 这里需要明确的几个点:1.货币只有 25 分、10 分、5 分和 1 分四种硬币;2.找给客户 41 分钱的硬币;3.硬币最少化思考,能使用我们今天学到的贪婪算法吗?怎么做? 按照贪心算法的三个步骤:1.41分,局部最优化原则,先找给顾客25分;2.此时,41-25=16分,还需要找给顾客10分,然后5分,然后1分;3.最终,找给顾客一个25分,一个10分,一个5分,一个1分 ^_^;总结:贪心算法的优缺点优点:简单,高效,省去了为了找最优解可能需要穷举操作,通常作为其它算法的辅助算法来使用;缺点:不从总体上考虑其它可能情况,每次选取局部最优解,不再进行回溯处理,所以很少情况下得到最优解

    46511

    贪心算法+回溯算法

    贪心算法 先来比较一下贪心算法和动态规划 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择,不考虑整体,只考虑局部最优,所以它不一定能得到最优解; 动态规划则是每个步骤都要进行一次选择,但选择通常要依赖子问题的解 所以一般选自自底向上自带备忘的机制,所以一定是最优解; 最优子结构的概念 如果一个问题的解包含其子问题的最优解,则称该问题具有最优子结构,也就是求解大问题的解,是通过求解小问题取解决 如果理解了最优子结构,则会发现贪心算法和动态规划都利用了最优子结构的性质 实现该算法的过程 从问题的某一初始解出发 while 能朝给定总目标前进一步 do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 典型的可用贪心来解的问题有 最小生成树、分数背包问题( 所以先选择B,再选择A  再从C中选择5   这时价值肯定最大 但贪心算法一开始就说了,并不保证最优解,所以有时会配合随机算法算法导论第三版第五章有讲)使用  一般来说贪心算法的代码比动态规划简单的多 这是解集合树(具体怎么解决这个问题,再分子界限算法中解决,这里只是介绍回溯法本身) ?

    78491

    浅析常见的算法范式

    算法逻辑分为三个步骤: 定义子问题。 重复解决子问题。 识别并解决基本问题。 动态规划案例:最小硬币找零问题 这是一个名为为硬币找零问题的常见面试题。 硬币找零问题是给定找零的金额,找出可以用多少特定数量的硬币来找零的方式。最小硬币找零问题只是找到使用给定面额的钱所需的最少硬币数量。 贪心算法与当前的最优解决方案相关,并试图找到一个全局的最佳方案。 贪心算法倾向于简单直观,但可能不是整体最优的解决方案。 贪心算法案例:最小硬币找零问题 上面用动态规划解决的硬币问题也可以用贪心算法解决。这个解决方案的是否能得到最优解取决于所采用的面额。 贪心算法比动态规划算法要简单而且更快,但是得到的有可能不是最优解。 回溯算法 回溯算法非常适合逐步查找和构建解决方案。 尝试以一种方式解决问题。

    31921

    洛谷P2851 最少硬币The Fewest Coins(完全背包+多重背包)

    为了高效地完成任务,他想使硬币的转手次数最少。即使他交付的硬 币数与找零得到的的硬币最少。 John有Ci个面值为Vi的硬币( )。我们假设店主有无限多的硬币, 并总按最优方案找零。

    58750

    经典算法贪心算法

    什么是贪心算法?   贪心算法,又称贪婪算法(Greedy Algorithm),是指在对问题求解时,总是做出在当前看来是最好的选择。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。 贪心算法适用的问题   贪心策略适用的前提是:局部最优策略能导致产生全局最优解。也就是当算法终止的时候,局部最优等于全局最优。 如果确定可以使用贪心算法,那一定要选择合适的贪心策略; 贪心算法的几个例子 1. 经我们分析,这种情况是不适合用贪心算法的,因为我们上面提供的贪心策略不是最优解。

    81330

    常用算法贪心算法

    因而选用贪心算法必须保证当前选的最好的必定是整体最好的。 示例 分发饼干 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 分析如下 为了使得整体时间最短,那么冷却时间肯定是最少的,因此要尽可能保证两个相同的任务之间的执行间隔为n。 换句话说就是贪心的选择执行n个不一样的任务,使得CPU能够充分利用 要选择先执行的任务,得考虑如何使得当前选择整体是最优的,加入随便选择一个任务A执行,当存在一个任务B它的任务数比选择的任务数要多时,这意味着 list.add(top); for (int i=0;i<maxLength;i++) { //贪心的选择没有执行过的 }else{ break; } } return Math.max(tasks.length,(taskArr[25]-1)*(n+1)+m); } 复制代码 附录 贪心算法思路

    28320

    ACM之贪心算法

    贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。 最终,取以上 22 轮遍历 left 和 right 对应学生糖果数的 最大值 ,这样则 同时满足左规则和右规则 ,即得到每个同学的最少糖果数量。 我们现在要用这些钱来支付 K 元,最少要用多少张硬币呢? 在生活中,我们肯定是先用面值最大的来支付,如果不够,就继续用更小一点面值的,以此类推,最后剩下的用 1 元来补齐。 问题: 要求:给定面额为1,5,10,50,100,500这六种面额的硬币,各3,2,1,3,0,2枚,现在用这些硬币支付A元,求使用最少硬币

    21020

    贪心算法问题-LeetCode 55、45(贪心算法,跳跃问题)

    贪心算法问题:LeetCode #55 #45 1 编程题 【LeetCode #55】跳跃游戏 给定一个非负整数数组,你最初位于数组的第一个位置。 算法原理: 遍历整个nums数组,每次计算从i位置的最大可能到达的距离,然后依次更新这个最大值,如果最大值大于nums的大小nums.size(),那么就返回true, 否则返回false. 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 说明: 假设你总是可以到达数组的最后一个位置 算法原理: 由于题目中规定总能到达数组的最后一个位置,因此我们在遍历数组时每次都要去找最大的跳跃位置,只有到达了这个最远的边界end,我们才让step进行自加

    67660

    贪心算法-LeetCode 134、111(递归算法,异或性质,贪心

    对于swap函数使用中间变量的形式大家都不陌生了,但是对于面试官来说这种方法不出奇,并不是面试官想要的!有没有不使用中间变量的呢? 在swap2函数中,我们可以...

    37020

    贪心算法秘籍

    换言之,贪心算法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。贪心算法能得到许多问题的整体最优解或整体最优解的近似解。因此,贪心算法在实际中得到大量的应用。 那么,贪心算法需要遵循什么样的原则呢? 2.1.2 贪亦有道 “君子爱财,取之有道”,我们在贪心算法中“贪亦有道”。 问题的最优子结构性质是该问题是否可用贪心算法求解的关键。 图2-1 原问题和子问题 2.1.3 贪心算法秘籍 武林中有武功秘籍,算法中也有贪心秘籍。上面我们已经知道了具有贪心选择和最优子结构性质就可以使用贪心算法,那么如何使用呢?下面介绍贪心算法秘籍。 不是贪心算法像冒泡排序,而是冒泡排序使用了贪心算法,它的贪心策略就是每一次从剩下的序列中选一个最大的数,把这些选出来的数放在一起,就得到了从大到小的排序结果,如图2-2所示。 ?

    53720

    最少数量的箭打破气球(贪心

    在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。 由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x...

    17920

    扫码关注腾讯云开发者

    领取腾讯云代金券