一个简单Oympiad问题的贪心算法 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

贪心算法问题-LeetCode 55、45（贪心算法，跳跃问题）

贪心算法问题：LeetCode #55 #45 1 编程题【LeetCode #55】跳跃游戏给定一个非负整数数组，你最初位于数组的第一个位置。...算法原理：遍历整个nums数组，每次计算从i位置的最大可能到达的距离，然后依次更新这个最大值，如果最大值大于nums的大小nums.size()，那么就返回true, 否则返回false....其中i的范围是：小于nums.size()同时还要小于从当前位置i可以到达的距离。这就是正常人取求解这个问题的思路，很容易想到的！...，你最初位于数组的第一个位置。...说明: 假设你总是可以到达数组的最后一个位置算法原理：由于题目中规定总能到达数组的最后一个位置，因此我们在遍历数组时每次都要去找最大的跳跃位置，只有到达了这个最远的边界end，我们才让step进行自加

1.4K6 0

活动安排问题--贪心算法

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。...贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。　　...也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。　　此算法的效率极高。...贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。...(1问题，每个时间都用一个正整数表示。

2.7K6 0

您找到你想要的搜索结果了吗？

是的

没有找到

贪心算法(集合覆盖问题)

首先来看一个集合覆盖问题：假如存在下面需要付费的广播台，以及广播台信号可以覆盖的地区，如何选择最少的广播台，让所有地区都可以接收到信号？...这个问题就是经典的用贪心算法求解的问题。贪心算法是指在每一步选择中都采取最优的策略，从而希望能够导致结果是最优的一种算法。贪心算法所得到的结果并不一定是最优的解，但都是相对接近最优解的结果。...在这32中组合中挑选一种可以覆盖到8个地区，并且广播台最少的组合，那就是本题的解了。这样做显然很麻烦，要是有100个广播台，那不是完犊子了。但是可以使用贪心算法，提高效率。...贪心算法步骤如下：遍历所有的广播台，找到一个包含了最多当前还未覆盖地区的广播台；将这个广播台存起来，想办法把该广播台覆盖的地区中下次选择时，用别的广播台代替；重复上面的步骤直到覆盖了所有的地区。...所以最终的选择结果是k1、k2、k3、k5。三、代码实现：将上面的问题用代码实现出来。

1.3K2 0

贪心算法之背包问题

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。...贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。...完全背包问题：给定n个物品和一个容量为C的背包，物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，与0-1背包的区别是，在完全背包问题中，可以将物品的一部分装入背包...设计算法的思路很简单，计算物品的单位价值，然后尽可能多的将单位重量价值高的物品放入背包中。...python实现代码如下： 1 # coding=gbk 2 # 完全背包问题，贪心算法 3 import time 4 __author__ = 'ice' 5 6 7 class

1.2K6 0

贪心算法之区间调度问题

什么是贪心算法呢？贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。...比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。...什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一小部分问题拥有这个性质。...一、问题概述言归正传，本文解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。...正确的思路其实很简单，可以分为以下三步：从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。

1.1K1 0

算法笔记（0002） - 【贪心算法】活动安排问题

算法笔记（0002） - 【贪心算法】活动安排问题贪心算法原理在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。...特性贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的...这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。...对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。...贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

1.2K2 1

使用贪心算法解决集合覆盖问题

在《算法图解》里面有一个蛮有意思的小案例，背景是一个广播节目，要让全美的50个周的听众都能够听到，但是每个电台可能覆盖多个州，每在一个电台播出就需要一笔费用，所以就是从成本的角度来看，怎么尽可能在所有的州都播出...，这是一个典型的集合覆盖的问题，而且在我们的生活中算是比较典型。...比如我们先缩小范围，指定5个州，那么50个州也是同样的算法。...如何使用贪心算法呢，就是选择覆盖尽可能多的州的电台，然后逐步缩小范围。那么覆盖面广的州所对应的电台就优先被选中，依次类推。...当然贪心算法得到的不是精确的结果，即可能不是最优解，算是一种近似算法，能够基本得到的最优解，而且效率很高。

1.2K2 0

【趣学算法】贪心算法、海盗古董装船问题

14天阅读挑战赛努力是为了不平庸~ 算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！...文章目录贪心本质贪心选择最优子结构最优装载问题 sort函数总结贪心本质一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择得到全局最优的解决方案。...——《算法导论》贪心选择贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到，也就是先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。...这种选择依赖于已做出的选择，但不依赖于未作出的选择。最优子结构最优子结构是指原问题的最优解包含子问题的最优解。如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有意义，无法采用贪心算法。...最优装载问题海盗们截获一艘装满各种各样古董的货船，每一件古董都价值连城，但一旦打碎就会失去其原有的价值。

3642 0

贪心算法-活动选择问题（Python实现）

# 有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源， # 如演讲会场等，而在同一时间内只有一个活动能使用这一资源。...# 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。 # 如果选择了活动i，则它在半开时间区间[si, fi]内占用资源。...# 若区间[si, fi]与区间[sj, fj]不相交，则称活动i与活动j是相容的。 # 也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。...# 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合， # 是可以用贪心算法有效求解的很好例子。 # 该问题要求高效地安排一系列争用某一公共资源的活动。...# 贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 import ioTool #编程任务：在所给的活动集合中选出最大的相容活动子集合。

1.1K2 0

贪心算法-分数背包问题（Python实现）

import ioTool def beibao(s,m,b): bb = 0 # 现在的背包容量 beibaoA = [] #放入背包的东西 #循环的i的范围不能超过传过来的数量...，并且背包的容量也不能超过预定的数量（例如：50，则只能小于等于50） i = 0 while i < len(s) and bb<=b: #判断是否已经放入背包了...m = [60, 100, 120] # 价值 b = 50 # 背包总容量 k = 0 beibao = beibao(s,m,b) print("背包中存入的:...", beibao[0]) print("背包的容量:", beibao[1]) for i in range(len(s)): print("从：商品",i,"取："

1.8K1 0

【趣学算法】Day3 贪心算法——背包问题

该篇文章收录专栏—趣学算法目录题目描述问题分析算法设计完美图解算法详解（1）确定合适的数据结构。（2）对物体按单位重量价值进行排序。...（3）使用贪心算法求解问题算法分析 ---- 题目描述有n种物品，每种物品只有一个，第i种物品的重量为 wi，价值为 vi，背包的容量为 w，物品可以分割。...因此，我们应采用第三种贪心策略——每次从剩下的物品中选单位重量价值最大的物品。算法设计（1）确定合适的数据结构并初始化。...cmp); //前两个参数分别为待排序数组的首地址和尾地址，cmp为比较函数（3）使用贪心算法求解问题 double solve (int n, double w) { double sum...//是用贪心算法求解问题 if(s[i].w 的重量小于或等于剩余容量 cleft -= s[i].w;

1.1K3 0

Python ---- 算法入门(1)贪心算法解决部分背包问题

一个小偷想到商店行窃，他的背包最多只能装 50 斤的商品，如何选择才能获得最大的收益呢？ 2. 解决问题的思路【贪心算法】贪心算法是每一步都追求最优的解决方案；如何选择是最优的商品？...【计算每个商品的收益率（收益/重量）】使用贪心算法进行选择！【优先选择收益率最大的商品】解决最终问题装够50斤！...【直至所选商品的总重量达到 50 斤】注意：虽然贪心算法每一步都是最优的解决方案，但整个算法并不一定是最优的。 3....计算每种商品装的量和对应量的价值 # 计算每种商品装的量和对应量的价值 def get_goods_result_and_value(w, goods_info): for item in goods_info...贪心算法解决部分背包问题的完整代码 ''' Descripttion: version: 1.0.0 Author: Rattenking Date: 2022-07-12 14:13:34 LastEditors

5292 0

剪视频剪出一个贪心算法……

这是个很有意思的区间算法问题，也是力扣第 1024 题「视频拼接」，题目如下：函数签名如下： int videoStitching(int[][] clips, int T); 记得以前写过好几篇区间相关的问题...贪心算法做时间管理写过利用贪心算法求不相交的区间。算上本文的区间剪辑问题，经典的区间问题也就都讲完了。...因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解。...区间问题特别容易用贪心算法，公众号历史文章除了贪心算法之区间调度，还有一篇贪心算法玩跳跃游戏，其实这个跳跃游戏就相当于一个将起点排序的区间问题，你细品，你细品。...以上就是这道题的解题思路，仔细想想，这题的核心和前文贪心算法玩跳跃游戏写的跳跃游戏是相同的，如果你能看出这两者的联系，就可以说理解贪心算法的奥义了。

2732 0

用Java解决贪心算法——删数问题

贪心算法——删数问题【问题描述】假设正整数n、s，s算法对任一给定n位数，删除其中的s位后，使得剩下的位新数最小。...【输入形式】 ex：1 2 3 9 5；删掉一个数； 1：1 2 3 5 2：1 2 3 3：1 2 【个人思路】从第一个数开始遍历，到寻找到单调递减的第一个数（即单调递增的最后一个数），则删除，若无单调递减子序列...，则删掉最后一个非递减序列的数；每找到一个就又从头开始。...即每做一次删数，就是一次贪心选择，删掉此数剩下的数为组成最小【代码演示】 import java.util.Scanner; public class shanshuwenti2 { public

2962 0

贪心算法最优装载问题（Java代码实现）

最优装载问题最优装载问题实质上就是一个简单版的0-1背包问题问题描述有一批集装箱要装上一艘载重量为 c 的轮船，其中集装箱 i 的重量为 wi 最优装载问题要求确定在装载体积不受限制的情况下...，将尽可能多的集装箱装上轮船算法描述可用贪心算法求解/* * 若尘 */ package loading; import java.util.Arrays; /** * 最优装载问题（贪心算法...public class LoadingProblem { private static int[] x; /\*\* \* \* @param c 总重量 \* @param w 每个集装箱的重量...if (this.w == o.w) return 0; else return 1; } } }最优值为: 10.0 最优解为： 1, 1, 0, 1, 1 采用重量最轻者先装的贪心选择策略...，可产生最优装载问题的最优解Java 源代码代码有详细注释，不懂评论下方留言

1.3K11 7

【趣学算法】Day2 贪心算法——最优装载问题

该篇文章收录专栏—趣学算法 ---- 目录一、贪心算法（1）介绍（2）注意事项（3）性质 1）贪心选择 2）最优子结构二、最优装载问题（1）古董重量排序（2）贪心策略选择模板代码（...1）分析（2）伪代码代码优化（1）分析（2）伪代码三、程序实现 ---- 一、贪心算法（1）介绍贪心算法总是做出当前最好的选择，期望通过局部最优解选择，从而得到全局最优的解决方案。...（3）性质人们通过实践发现，利用贪心算法求解的问题往往具有两个重要的性质：贪心选择和最优子结构。只要满足这两个性质，就可以使用贪心算法。...1）贪心选择贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到：先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。...贪心算法通过一系列的局部最优解（子问题的最优解）得到全局最优解（原问题的最优解），如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。

8661 0

剪视频剪出一个贪心算法…

这是个很有意思的区间算法问题，也是力扣第 1024 题「视频拼接」，题目如下：函数签名如下： int videoStitching(int[][] clips, int T); 记得以前写过好几篇区间相关的问题...贪心算法做时间管理写过利用贪心算法求不相交的区间。算上本文的区间剪辑问题，经典的区间问题也就都讲完了。...因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解。...区间问题特别容易用贪心算法，公众号历史文章除了贪心算法之区间调度，还有一篇贪心算法玩跳跃游戏，其实这个跳跃游戏就相当于一个将起点排序的区间问题，你细品，你细品。...以上就是这道题的解题思路，仔细想想，这题的核心和前文贪心算法玩跳跃游戏写的跳跃游戏是相同的，如果你能看出这两者的联系，就可以说理解贪心算法的奥义了。

6472 0

贪心算法(二)——一般背包问题

注：背包问题分为两种，若每个物体不可分割，则称为0/1背包问题，这种问题无法用贪心法求的最优解，只能求的近似解。而若每个物体可以切分，则称为一般背包问题，可以使用贪心法求的最优解。...下面讨论的就是一般背包问题。结果集一般背包问题中，结果集可以用一个n元组表示： 1. x的下标i表示物体的序号； 2. xi表示第i个物体加入背包的部分（0<=xi<=1） ?...目标函数使用贪心法解决最优化问题的第一步，就是要从题目中抽象出目标函数，这是一个数学建模的过程。本题中，目标函数就是当前背包收益的最大值： ?...lastBody = bodys.get(i); results.add(new Body(lastBody.id,rest,(lastBody.p*rest/lastBody.w)); } 总结要用贪心法解决一个最优化问题...若无法选出一个最优量度标准，则可以使用动态规划法解决最优化问题。

2.1K7 0

算法浅谈——怪盗基德的珠宝选择问题与贪心算法

他的包的体积是10，那么请问，基德应该采取什么策略呢？学过算法的同学会一眼就看出来，这是一个背包问题。 ? 我们假装没学过，就按照常理来分析。...所以正确的答案是应该先拿C再拿B，这样能够拿到的价值是11，否则只能装下A一个，价值是10。我们每次做决定的时候都选择当下回报最多的选项，这种算法叫做贪心法。...贪心法有反例这个结论并不难，很容易想明白，难的是我们如何判断当前的问题下，能不能使用贪心算法呢？尤其是我们可能一时半会想不出反例的情况下。...有一个比较取巧的方法叫做均等假设法，这个名字是我取的，没听说过很正常，不用纠结。事实上课本当中谈及贪心算法，也根本不会阐述这个问题，然而这个问题在实际当中又是非常重要的。那么，什么叫均等假设法呢？...很简单，就是假设我们在某次决策的时候，面临两个势均力敌的选项，我们通过判断这两个选项最终的结果是否一致来判断贪心算法是否成立。如果两个均等的选项最终结果一致，那么贪心算法可行，否则不可行。

6533 0

使用贪心算法解决最小生成树问题

今天跟大家聊一聊贪心算法问题，因为遇到这个面试题，问贪心算法解决最小生成树是怎么设计的，以及如何应用？好家伙，这面试官一上来就不按套路出牌，直接上难度，如果你遇到这样的问题，该怎么办呢。...## 贪心算法解决最小生成树问题的一般步骤**一、解决思路**1. **初始化**： - 选择一个起始顶点，将其加入到已访问集合（通常记为 `visited`）中。...## 贪心算法解决最小生成树问题的时间复杂度是多少以下是贪心算法解决最小生成树问题的时间复杂度分析：**一、Prim 算法**- **朴素实现**： - 对于一个具有 `n` 个顶点和 `m` 条边的图...## 贪心算法解决最小生成树问题的优缺点是什么**一、优点**：- **简单高效**： - 贪心算法解决最小生成树问题，如 Prim 算法和 Kruskal 算法，相对比较简单易懂，易于实现和编码...综上所述，贪心算法解决最小生成树问题在静态图的场景下通常表现良好，具有简单、高效、利用最优子结构的优点，但对于动态图的适应性较差，并且其性能受图存储结构和所需数据结构的维护的影响，在编程实现上也需要一定的技巧和考虑因素

962 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭