barriers / 阅读 / 详情

贪婪启发式和贪婪算法的区别是什么?

2023-08-12 23:35:47
共1条回复
clou

  马踏棋盘的问题很早就有人提出,且早在1823年,J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时,优先选择‘出口"最小的进行搜索,‘出口"的意思是在这些子结点中它们的可行子结点的个数,也就是‘孙子"结点越少的越优先跳,为什么要这样选取,这是一种局部调整最优的做法,如果优先选择出口多的子结点,那出口少的子结点就会越来越多,很可能出现‘死"结点(顾名思义就是没有出口又没有跳过的结点),这样对下面的搜索纯粹是徒劳,这样会浪费很多无用的时间,反过来如果每次都优先选择出口少的结点跳,那出口少的结点就会越来越少,这样跳成功的机会就更大一些。这种算法称为为贪心算法,也叫贪婪算法或启发式算法,它对整个求解过程的局部做最优调整,它只适用于求较优解或者部分解,而不能求最优解。这样的调整方法叫贪心策略,至于什么问题需要什么样的贪心策略是不确定的,具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高,如果只要求出一个解甚至不用回溯就可以完成,因为在这个算法提出的时候世界上还没有计算机,这种方法完全可以用手工求出解来,其效率可想而知。

  贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。

  贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式

  所以需要说明的是,贪心算法可以与随机化算法一起使用,具体的例子就不再多举了。其实很多的智能算法(也叫启发式算法),本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解,但是比单纯的贪心算法更靠近了最优解。例如遗传算法,模拟退火算法。

相关推荐

贪心算法求解问题时应考虑的问题有哪些?

贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。1、贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。2、贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。3、每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止。4、贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能。贪心算法的基本要素:1、贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。2、贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。3、当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。4、问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响,而动态规划则不是。
2023-08-08 05:22:591

贪心算法的基本思想

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性:1、随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后,目标函数给出解的值。
2023-08-08 05:23:451

贪心算法的基本要素

贪心算法的基本要素:贪心选择性质和最优子结构性质。1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。2、最优子结构性质当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。贪心算法的局限性和分析过程1、贪心算法的局限性:贪心算法有他的局限性,有的时候我们选择局部的最优解,但是它对与全局并非最优解,就比如硬币找零问题。但是我们依然可以用我们上一章所学的动态规划思想来解决。2、贪心算法的分析过程:首先,我们需要确定我们的贪心策略,只有正确的贪心策略才能得出我们的结论。
2023-08-08 05:24:061

贪心算法的本质

1. 贪心法(Greedy Algorithm)定义 求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多种选择; 贪心法就是这样的算法:它在每个决策点作出在当时看来最佳的选择,即总是遵循某种规则,做出局部最优的选择,以推导出全局最优解(局部最优解->全局最优解)2. 对贪心法的深入理解 (1)原理:一种启发式策略,在每个决策点作出在当时看来最佳的选择 (2)求解最优化问题的两个关键要素:贪心选择性质+最优子结构 ①贪心选择性质:进行选择时,直接做出在当前问题中看来最优的选择,而不必考虑子问题的解; ②最优子结构:如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质 (3)解题关键:贪心策略的选择 贪心算法不是对所有问题都能得到整体最优解的,因此选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。 (4)一般步骤: ①建立数学模型来描述最优化问题; ②把求解的最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解; ③证明做出贪心选择后: 1°原问题总是存在全局最优解,即贪心选择始终安全; 2°剩余子问题的局部最优解与贪心选择组合,即可得到原问题的全局最优解。 并完成2°3. 贪心法与动态规划 最优解问题大部分都可以拆分成一个个的子问题,把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法,我们自底向上构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始,选择最优的路,一直走到底就可以了。
2023-08-08 05:24:261

什么是贪心算法?

问题一:贪心算法,这个贪心到底是什么意思 贪心指目光短浅,只看到当前这一步的最优决策,而不考虑以后的决策。这样的算法只在特定的问题下是正确的。 问题二:哪些常见算法属于贪婪算法? 显然KMP和FLOYD算法不是贪心算法,FLOYD算法是使用了类似于动态规划的思想,而KMP算法则是对串的前缀进行去处理得到所有可能出现匹配的位置从而减少不必要的位移。贪心算法可能还有很多,但是一般能用到的可能只有这些。在确定一个问题是否能用贪心来解决的时候应该线能够证明在这里使用贪心算法的正确性(详见算法导论) 问题三:求解一贪心算法问题 最快回答那个不懂别乱说,别误人子弟。 这题标准的贪心算法,甚至很多时候被当做贪心例题 要求平均等待时间,那么就得用 总等待时间 / 人数 所以只用关心总等待时间, 如果数据大的在前面,那么后面必然都要加一次这个时间,所以按从小到大排。 给你写了个,自己看吧。 #include stdafx.h #include #include #include using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int n; float arr[105]; cin >> n; for(int i = 0; i > arr[i]; sort(arr, arr+n); int tnow = 0; int tmax = 0; for(int i = 0; i 问题四:贪心算法的基本思想是什么? 自己利益最大 问题五:贪心算法是什么?求教学,c语言 jb51/article/71144,里面讲得比较详细 问题六:贪心算法的基本要素是什么,并简单解释其含义 您好,我看到您的问题很久没有人来回答,但是问题过期无人回答会被扣分的并且你的悬赏分也会被没收!所以我给你提几条建议: 一,你可以选择在正确的分类下去提问,这样知道你问题答案的人才会多一些,回答的人也会多些。 二,您可以到与您问题相关专业网站论坛里去看看,那里聚集了许多专业人才,一定可以为你解决问题的。 三,你可以向你的网上好友问友打听,他们会更加真诚热心为你寻找答案的,甚至可以到相关网站直接搜索. 四,网上很多专业论坛以及知识平台,上面也有很多资料,我遇到专业性的问题总是上论坛求解决办法的。 五,将你的问题问的细一些,清楚一些!让人更加容易看懂明白是什么意思! 谢谢采纳我的建议! ! 问题七:贪心算法的特性 贪婪算法可解决的问题通常大部分都有如下的特性:⑴随着算法的进行,将积累起其它两个 *** :一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。⑵有一个函数来检查一个候选对象的 *** 是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑶还有一个函数检查是否一个候选对象的 *** 是可行的,也即是否可能往该 *** 上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑸最后,目标函数给出解的值。⑹为了解决问题,需要寻找一个构成解的候选对象 *** ,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的 *** 为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果 *** 中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到 *** 里。每一次都扩充 *** ,并检查该 *** 是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。
2023-08-08 05:24:341

数据结构之贪心算法

贪婪算法(Greedy)的定义:是一种在每一步选中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。 贪婪算法:当下做局部最优判断,不能回退 (能回退的是回溯,最优+回退是动态规划) 由于贪心算法的高效性以及所求得答案比较接近最优结果,贪心算法可以作为辅助算法或解决一些要求 结果不特别精确的问题 注意:当下是最优的,并不一定全局是最优的。举例如下: 有硬币分值为10、9、4若干枚,问如果组成分值18,最少需要多少枚硬币? 采用贪心算法,选择当下硬币分值最大的:10 18-10=8 8/4=2 即:1个10、2个4,共需要3枚硬币 实际上我们知道,选择分值为9的硬币,2枚就够了 18/9=2 如果改成: 背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下: 部分背包:某件物品是一堆,可以带走其一部分 0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走(没有选择它),不存在只带走一部分的情况。 部分背包问题可以用贪心算法求解,且能够得到最优解。 假设一共有N件物品,第 i 件物品的价值为 Vi ,重量为Wi,一个小偷有一个最多只能装下重量为W的背包,他希望带走的物品越有价值越好,可以带走某件物品的一部分,请问:他应该选择哪些物品? 假设背包可容纳50Kg的重量,物品信息如下表: 将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品 按照我们的贪心策略,单位重量的价值排序: 物品A > 物品B > 物品C 因此,我们尽可能地多拿物品A,直到将物品1拿完之后,才去拿物品B,然后是物品C 可以只拿一部分..... 在不考虑排序的前提下,贪心算法只需要一次循环,所以时间复杂度是O(n) 优点:性能高,能用贪心算法解决的往往是最优解 缺点:在实际情况下能用的不多,用贪心算法解的往往不是最好的 针对一组数据,我们定义了限制值和期望值,希望从中选出几个数据,在满足限制值的情况下,期望值最大。 每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据(局部最优而全局最优) 大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,也不需要严格的数学推导证明 在实际情况下,用贪心算法解决问题的思路,并不总能给出最优解
2023-08-08 05:24:411

贪心算法几个经典例子

贪心算法经典例子如下:活动安排问题是可以用贪心算法有效求解的一个很好的例子,该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合e=(1,2,…,n),其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间(si,fi)内占用资源。活动安排问题若区间(si,fi)与区间(sj,fj)不相交,则称活动i与活动j是相容的。也就是说,当si≥fi或sj≥fj时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。在下面所给出的解活动安排问题的贪心算法gpeedyselector中,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序:f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列,我们可以用o(nlogn)的时间将它重排。
2023-08-08 05:24:491

分治、贪心五大算法

1、分治 分治(即分而治之),把一个复杂的问题分成多个相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 适用场景:二分搜索、归并排序、快速排序、大整数乘法、第K小元素、最近点对、快速傅里叶变换等。 2、动态规划 动态规划法也是把问题一层一层地分解为规模逐渐减小的同类型的子问题。动态规划通常用来求最优化问题。此类问题可以有很多可行解,我们求出的是一个最优解,可能存在多个最优解。(最优子结构、公共子问题) 与分治法的区别是:分治的子问题是相互独立的,动态规划最好解决有公共子问题的,子问题相关性很大。 使用场景:矩阵连乘、钢条切割、最长公共子序列、最优二叉搜索树、流水作业调度、0/1背包问题等。 维特比算法是动态规划在HMM中的应用,维特比算法用于解决HMM的预测或者叫解码问题。 viterbi有最优解是因为HMM每一步是条件独立的!既然后面的概率和前面的没关系,那前面选最大的概率就行了。 而beam search时后面的概率依赖于前面所有的词,相当于n-gram是满的,viterbi的n-gram是2 背包问题: https://blog.csdn.net/wind__chaser/article/details/89457771 https://blog.csdn.net/qq_38410730/article/details/81667885 3、贪心 通过局部最优选择达到全局最优选择。贪心算法不一定总产生最优解,贪心算法是否产生优化解,需严格证明贪心算法产生最优解的条件:(最优子结构、贪心选择性) 贪心选择性:当一个问题的全局最优解可以通过局部最优解得到,称这个问题具有贪心选择性。 适用场景:活动选择问题、哈夫曼编码问题、最小生成树问题、单源最短路径问题等。 贪心算法:softmax之后取最大概率。与之对应的是,Beam Search算法 http://www.360doc.com/content/18/0618/09/17563728_763230413.shtml https://blog.csdn.net/qq_16234613/article/details/83012046 https://www.zhihu.com/question/54356960 分治和动态规划的区别: 动态规划也是一种分治思想(比如其状态转移方程就是一种分治),但与分治算法不同的是,分治算法是把原问题分解为若干个子问题, 自顶向下求解子问题,合并子问题的解,从而得到原问题的解。动态规划也是把原始问题分解为若干个子问题,然后自底向上, 先求解最小的子问题,把结果存在表格中,在求解大的子问题时,直接从表格中查询小的子问题的解,避免重复计算,从而提高算法效率。 动态规划和分治法有些相像,都是把一个问题分成了很多子问题来求解,但是不同的是动态规划会记忆之前解决的子问题的结果, 避免了重复计算。判断一个问题是否能用动态规划求解,要看它是否能划分成合适的子问题,然后写出递推关系式。 动态规划得到的解一定是最优解。
2023-08-08 05:25:031

贪心算法缺点

贪心算法缺点:不从总体上考虑其它可能情况,每次选取局部最优解,不再进行回溯处理,所以很少情况下得到最优解。这算法不懂得深谋远虑,自然可能走不到最好的结果啦。贪心算法的优点:优点:简单,高效,省去了为了找最优解可能需要穷举操作,通常作为其它算法的辅助算法来使用。贪心算法基本步骤:步骤1:从某个初始解出发;步骤2:采用迭代的过程,当可以向目标前进一步时,就根据局部最优策略,得到一部分解,缩小问题规模;步骤3:将所有解综合起来。
2023-08-08 05:25:201

五大常用算法之一:贪心算法

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。比如, 求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法 。 贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。 可惜的是,它需要证明后才能真正运用到题目的算法中。 一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。 对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下: 贪心策略:选取价值最大者。反例: W=30 物品:A B C 重量:28 12 12 价值:30 20 20 根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。 (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。 (3)贪心策略:选取单位重量价值最大的物品。反例: W=30 物品:A B C 重量:28 20 10 价值:28 20 10 根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决. 所以需要说明的是,贪心算法可以与随机化算法一起使用,具体的例子就不再多举了。(因为这一类算法普及性不高,而且技术含量是非常高的,需要通过一些反例确定随机的对象是什么,随机程度如何,但也是不能保证完全正确,只能是极大的几率正确)。
2023-08-08 05:26:111

活动选择(贪心算法)

参考: 【算法导论】贪心算法之活动选择问题 贪心算法(Greedy Algorithm)在每一步都做出当时看起来最佳的选择,寄希望这样的选择能导致全局最优解。 这种算法并不能保证得到最优解,但对很多问题确实可以求得最优解。 假定有一个n个活动的集合S={a1,a2,a3,...,an},这些活动 使用同一个资源 ,而这个资源在某个时刻 只能给一个活动使用 。每个活动都有一个 开始时间si 和一个 结束时间fi ,其中0<=si<fi<=∞。 如果活动ai被选中,则此活动发生在 半开区间[si,fi) 中。 若两个活动ai和aj的 时间区间不重叠 ,则称这两个活动是 兼容 的 在活动选择问题中,我们希望选出一个最大兼容活动集。 假定活动已经按照 结束时间递增顺序 排好序 f1<=f2<=f3<=...<=fn 考虑如下例子: 可以看到,{a3,a9,a11}是由相互兼容的活动组成。但它不是一个最大集,{a1,a4,a8,a11}更大,是一个最大集。(最大集不唯一) 假设:Sij表示在ai结束之后,在aj开始之前的活动的 集合 。Aij表示Sij的一个最大相互兼容的活动子集。 那么只要Sij非空,则Aij至少会包含一个活动,假设为ak。那么可以将Aij分解为:Aij = Aik+ak+Akj。 假设Cij为Aij的大小,那么有Cij=cik+ckj+1。 于是,我们可以利用动态规划得到这个问题的递归解 我们当然可以利用动态规划自底向上地求解这个问题,但是我们可以利用贪心算法更快地求解问题答案。 我们选择活动 结束时间最早 的那个活动,这样能够给其他活动尽可能的腾出多余的时间,而后每一步都在剩下的活动中选取最早的活动,这样就可以获得一个最优解。 为什么贪心选择——最早结束的活动ai——总是最优解的一部分呢? 假设Aij是Sij的某个最大兼容活动集,假设Aij中,最早结束的活动是an。(an是最优解中最早结束的,不一定是原先活动中最早结束的)我们要证明我们选择的a1(原先活动集中最早结束的)也在最优解中。 分两种情况: ①如果an=a1,则得证 ②如果an不等于a1,则an的结束时间一定会 晚于 a1的结束时间,我们用a1去 替换 Aij中的an,于是得到A",由于a1比an结束的早,而Aij中的其他活动都比an的结束时间开始 的要晚,所以A"中的 其他活动 都与a1不相交 ,所以A"中的所有活动是兼容的,所以A`也是Sij的一个最大兼容活动集。 (简单说,就是用a1 替换 an,得到另一个解A",由于a1最早结束,当然与其他活动不相交,于是A"也兼容且个数和A一样,所以A"也是最优解) 于是证明了命题。 通过以上分析,我们可以反复地选择最先结束的活动,保留于此活动兼容的活动,重复执行,直到不再有剩余活动。 贪心算法通常是 自顶向下 地设计:做出一个选择,然后求解剩下的那个子问题 为了方便初始化,我们添加一个虚拟活动a0,其结束时间为f0=0 由于我们之前就已经将活动按结束时间排好序,每一次找元素都只对元素访问一次,所以贪心算法的时间复杂度是大theta(n)
2023-08-08 05:26:181

(三) 贪心算法

贪心算法的思想非常简单且算法效率很高,在一些问题的解决上有着明显的优势。 假设有3种硬币,面值分别为1元、5角、1角。这3种硬币各自的数量不限,现在要找给顾客3元6角钱,请问怎样找才能使得找给顾客的硬币数量最少呢? 你也许会不假思索的说出答案:找给顾客3枚1元硬币,1枚5角硬币,1枚1角硬币。其实也可以找给顾客7枚5角硬币,1枚1角硬币。可是在这里不符合题意。在这里,我们下意识地应用了所谓贪心算法解决这个问题。 所谓贪心算法,就是 总是做出在当前看来是最好的选择(未从整体考虑) 的一种方法。以上述的题目为例,为了找给顾客的硬币数量最少,在选择硬币的面值时,当然是尽可能地选择面值大的硬币。因此,下意识地遵循了以下方案: (1)首先找出一个面值不超过3元6角的最大硬币,即1元硬币。 (2)然后从3元6角中减去1元,得到2元6角,再找出一个面值不超过2元6角的最大硬币,即1元硬币。 (3)然后从2元6角中减去1元,得到1元6角,再找出一个面值不超过1元6角的最大硬币,即1元硬币。 (4)然后从1元6角中减去1元,得到6角,再找出一个面值不超过6角的最大硬币,即5角硬币。 (5)然后从6角中减去5角,得到1角,再找出一个面值不超过1角的最大硬币,即1角硬币。 (6)找零钱的过程结束。 这个过程就是一个典型的贪心算法思想。 贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的 局部最优解 ,而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注:贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。) 贪心算法没有固定的算法框架,算法设计的关键是 贪心策略的选择 。选择的贪心策略必须具备无后效性。 贪心策略 适用的前提 是: 严格意义上讲,要使用贪心算法求解问题,该问题应当具备以下性质: 注意 :对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。 因此, 选择能产生问题最优解的最优量度标准是使用贪婪算法的核心 。 实际上,贪心算法 适用的情况很少 。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。 最优解问题大部分都可以拆分成一个个的子问题(多阶段决策问题),把解空间的遍历视作对子问题树的遍历,则以某种形式对树整个的遍历一遍就可以求出最优解,大部分情况下这是不可行的。 贪心算法和动态规划本质上是对子问题树的一种修剪,两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解,对于这个子问题本身肯定也是最优的)。 动态规划方法代表了这一类问题的一般解法, 自底向上 构造子问题的解,对每一个子树的根,求出下面每一个叶子的值,并且以其中的最优值作为自身的值,其它的值舍弃。 而贪心算法是动态规划方法的一个特例,可以证明每一个子树的根的值不取决于下面叶子的值,而只取决于当前问题的状况。换句话说,不需要知道一个节点所有子树的情况,就可以求出这个节点的值。由于贪心算法的这个特性,它对解空间树的遍历不需要自底向上,而只需要自根开始( 自顶向下 ),选择最优的路,一直走到底就可以了。 一个问题分为多个阶段,每个阶段可以有n种决策,各个阶段的决策构成一个决策序列,称为一个策略。 这两种算法都是选择性算法,在进行决策的选择时: 前提是这个问题得具有贪心选择性质,需要证明(数学归纳法(第一、第二)),如果不满足那就只能使用动态规划解决。(一旦证明贪心选择性质,用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。) 从范畴上来看: Greedy u2282 DP u2282 Searching (贪心是动规的特例) 即所有的贪心算法问题都能用DP求解,更可以归结为一个搜索问题,反之不成立。 贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解,与回溯法等比较,它的适用区域相对狭窄许多,因此正确地判断它的应用时机十分重要。 一步一步地进行,常 以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况 ,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。 它采用 自顶向下 ,以 迭代 的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以 贪心法不需要回溯 。 【问题描述】 马的遍历问题。在8×8方格的棋盘上,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。 【贪心算法】 其实马踏棋盘的问题很早就有人提出,且早在1823年,J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时,优先选择‘出口"最小的进行搜索,‘出口"的意思是在这些子结点中它们的可行子结点的个数,也就是‘孙子"结点越少的越优先跳,为什么要这样选取,这是一种局部调整最优的做法,如果优先选择出口多的子结点,那出口少的子结点就会越来越多,很可能出现‘死"结点(顾名思义就是没有出口又没有跳过的结点),这样对下面的搜索纯粹是徒劳,这样会浪费很多无用的时间,反过来如果每次都优先选择出口少的结点跳,那出口少的结点就会越来越少,这样跳成功的机会就更大一些。
2023-08-08 05:26:261

贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序,依次序每次取一条三角剖分的边,直至达到要求的边数。以下是两种贪心算法的主要步骤。3.2.2.1 贪心算法1第一步:设置一个记录三角剖分中边的数组T。第二步:计算点集S中所有点对之间的距离d(pi,pj),1≤i,j≤n,i≠j,并且对距离从小到大进行排序,设为d1,d2,…,dn(n-1)/2,相应的线段记为e1,e2,…,en(n-1)/2,将这些线段存储在数组E中。第三步:从线段集E中取出长度最短的边e1存到T中作为三角剖分的第一条边,此时k=1。第四步:依次从E中取出长度最短的边ek,与T中已有的边进行求交运算,如果不相交则存到T中,并从E中删除ek。这一步运行到S中没有边为止,即至k=n(n-1)/2。第五步:输出T。该算法中,第二步需要计算n(n-1)/2次距离,另外距离排序需要O(n2lgn)次比较。T中元素随第四步循环次数的增加而增加,因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分,那么第四步循环所需要的判定两条线段是否相交的次数为1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n3)在常数时间内可以判定两条线段是否相交,因此该算法的时间复杂性为O(n3)。3.2.2.2 贪心算法2第一步:求点集的凸壳,设凸壳顶点为p1,p2,…,pm,凸壳的边为e1,e2,…,em。并将凸壳顶点按顺序连接成边的ei加入T(三角剖分的边集合),并且ei的权值被赋为1。凸壳内点的集合为S1={pm+1,pm+2,…,pn}。第二步:从内部点S1中任取一点pi,求与pi距离最近的点pj,将线段 存入T。第三步:求与pj距离最近的点(除点pi外),设为pk,并将线段 存入T,pipjpk构成一个三角形,并将三条边wij、wjk和wki的权值设为1。第四步:分别求与pi、pj和pk距离最近的点(除点pi、pj和pk本身外),设为p"i,p"j,p"k,将 加入T,并将这些边的权值设为1,而wij、wjk和wki的值加1,即为2。边的权值为2则表示该边为两个三角形共有。第五步:对权值为1的边(除e1,e2,…,em外)的两个端点分别求与其距离最近的点,并将其连线(得到新的三角形)加入T,新三角形边的权值加1。第六步:对权值为1的边重复上一步,当一条边被使用一次其权值增加1,直到所有边的权值均为2为止(除e1,e2,…,em外)。贪心算法2中,第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求pk要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n2)
2023-08-08 05:26:351

求解一道贪心算法

强人就是弓虽
2023-08-08 05:26:591

简述贪心,递归,动态规划,及分治算法之间的区别和联系

联系:都是问题求解之时的一种算法。区别:一、作用不同1、贪心算法:把子问题的解局部最优解合成原来解问题的一个解。2、递归算法:问题解法按递归算法实现。如Hanoi问题;数据的结构形式是按递归定义的。如二叉树、广义表等。3、动态规划:动态规划算法通常用于求解具有某种最优性质的问题。4、分治算法:可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。二、方法不同1、贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。2、递归算法:通过重复将问题分解为同类的子问题而解决问题。3、动态规划:将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。4、分治算法:将一个规模为N的问题分解为K个规模较小的子问题。三、特点不同1、贪心算法:根据题意选取一种量度标准。2、递归算法:递归就是在过程或函数里调用自身。3、动态规划:虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。4、分治算法:原问题可以分解为多个子问题;原问题在分解过程中,递归地求解子问题;在求解并得到各个子问题的解后。
2023-08-08 05:27:171

贪心算法:有一个n个不等整数的数组,每次删a,b,加入a*b+1,如此下去直到剩最大的一个数存在。给出算法!

假设 [a,b,c,d,e,....]第一次后:[ab+1,c,d,e...]第二次后:[abc+c+1,d,e...]第三次后:[abcd+cd+d+1,e...] 根据规律,最后的结果为 abcd...n +cd...n+d..n +...+1所以最大的数即为求上述运算式的结果,程序算法为:int result=0;for(int i=0;i<数组.length;i++){ int tmp=1; if(i==0) { for(int j=i;j<数组.length;j++) { tmp*=数组[j]; } } else if(i==1) continue; else if(i==数组.length-1) tmp=1; else { for(int j=i+2;j<数组.length;j++) { tmp*=数组[j]; } } result +=tmp; }
2023-08-08 05:27:312

贪心算法总结 Greedy Algorithms

反证法: 假设贪心不是最优解: 先考虑如何排序 Exchange argument:通过交换元素将最优解转换为贪心解,但还保持最优性 当cache中不存在所需元素时,需要访问cache交换元素。 目标:cache misses的次数最少 最优算法:cache miss时替换当前future queries中最远访问的元素。 e.g. future queries中第一个元素g出现cache miss, 需要exchange,判断current cache中需要替换哪个元素。 在future queries中 思路:构造最优规划 ,它有最小的cache misses次数;Farthest-In-Future规划 ,两者在前 个请求的序列是相同的,如果能证明在第 步时, 可以转化为 并且没有增加cache misses的次数,则可以说明 是最优解。 最开始,假设 和 中元素如下: Case 1: 元素已经在Cache中 假设下一个请求的元素是d显然两者都不会发生cache miss,故两者总的cache misses次数还是相同; Case 2: 元素不在Cache中, 和 与外界交换相同的元素 假设下一个请求的元素是e,两者都用a与其交换,有 和 都增加了一次cache misses,故总cache misses次数还是相同; Case 3: 元素不在Cache中, 和 与外界交换不同的元素 假设下一个请求的元素是e, 交换a, 交换b,有 之后,下一个请求的元素有四种情况: Case 3a: 元素在 中, 不在 中; S交换a 也就是请求b,这时S用a交换b,有 有两次cache misses,而 只有一次,之后 和 序列又保持一致; Case 3b: 元素在 中, 不在 中; S不交换a 也就是请求b,S用c交换b,有 用a交换c,有 两者cache misses次数相同,之后 和 序列又保持一致 Case 3c: 元素在 中, 不在 中 即请求a,这种情况不可能发生,因为S_{FF}移出的是最远需要的元素,即request中a会排在b之后; Case 3d: 元素不在 和 中 假设请求f, 用a交换f, 用b交换f,有 两者cache misses次数相同,之后 和 序列又保持一致 的cache misses次数不会多于最优解 , 即 是最优解。 Single-link k-clustering 算法:
2023-08-08 05:27:381

贪心算法马的遍历 时间复杂度

马的遍历还有贪心算法么?我没听过,说来听听?长见识了,谢谢楼上的!
2023-08-08 05:27:572

哈夫曼编码(贪心算法)

参考: 哈夫曼编码 哈夫曼编码是一种十分有效的编码方法,广泛应用于 数据压缩 中 通过采用 不等长 的编码方式,根据 字符频率的不同 ,选择 不同长度的编码 ,对频率 越高 的字符采用 越短 的编码实现数据的高度压缩。 这种对频率越高的字符采用越短的编码来编码的方式应用的就是贪心算法的思想。 下面看一个例子: 假如我们有一个包含1000个字符的文件,每个字符占1个byte(1byte=8bits),则存储这100个字符一共需要8000bits。这还是有一些大的 那我们统计一下这1000个字符中总共有多少种字符,原来需要8bit来表示一个字符,如果使用更少的位数来表示这些字符,则可以减少存储空间。 假设这1000个字符中总共有a、b、c、d、e、f共6种字符,使用使用3个二进制位来表示的话,存储这1000个字符就只需要3000bits,比原来更节省存储空间。 或许还可以再压缩一下: 根据字符出现的 频率 给与字符 不等长 的编码,频率越高的字符编码越短,频率越低的字符编码越长。 它不能像等长编码一样直接按固定长度去读取二进制位,翻译成字符,为了能够准确读取翻译字符,它要求一个字符的编码不能是另外一个字符的前缀。 假设a、b、c、d、e、f这6个字符出现的频率依次降低,则我们可以给与他们这样的编码 假如字符的出现频率如图所示,按照这样的编码表示的话,总位数如图,一共2100bits,更加节省空间了 贪心策略:频率小的字符,优先入队。 步骤: 1.将每一个字符作为节点,以出现频率大小作为权重,将其都放入 优先队列 中(一个最小堆); 2.每次出队两个节点并创建一个父节点,使其权值为刚刚出队的节点的权值和,并且为两个节点的父节点(合并)。然后将这个树入队。 3.重复操作2,直到队列中只有一个元素(此时这个元素表示形式应该为一个树)时,完成创建。 创建好了树,该怎么编码呢? 我们对一个哈夫曼树,从父节点开始的所有节点,往左边标0,右边标1。那么到达叶子节点的顺次编码就可以找到了。 C:字符集合 Q:优先队列 EXTRACT-MIN:传入一个队列,出队最小的元素 INSERT:将z插入到Q中 当for循环结束之后,此时队列中只有一个元素,就是我们需要的哈夫曼树,最后返回此树即可。 假设T树已经是一个最优的树,假设x、y的频率小于等于最低处的a、b,然后交换x、a,y、b。 计算代价是否发生变化。 比如这里比较 T 变成 T " 后代价是否变化,发现代价变小或不变。 同理T"到T"",又因为T本来假设就是最优的,所以只能相等 所以T""也应该符合条件,即贪婪算法,每次取最小的两个节点出来这种做法是正确的
2023-08-08 05:28:051

贪心算法及其应用

求解一个问题时有多个步骤,每个步骤都选择当下最优的那个解,而不用考虑整体的最优解。通常,当我们面对的问题拥有以下特点的时候,就可以考虑使用贪心算法。 比如,我们举个例子,仓库里面总共有五种豆子,其对应的重量和总价值如下,现在我们有一个可以装100KG重量的袋子,怎么装才能使得袋子中的豆子价值最大? 我们首先看看这个问题是否符合贪心算法的使用场景?限制值是袋子100KG,期望值是袋子里面的价值最高。所以是符合的。那么我们尝试着应用下贪心算法的方法,每一个步骤都寻找当下的最优解,怎么做呢? 把仓库里面的每种豆子价值除以重量,得出每种豆子的单价,那么当下的最优解,肯定是尽可能最多地装单价最贵的,也就是先把20KG的黄豆都装上,然后再把30KG的绿豆都装上,再装50KG的红豆,那么此时正好装满袋子,总价值将是270元,这就是通过贪心算法求解的答案。 贪心算法的应用在这个问题上的求解是否是最优解需要一个很复杂的数学论证,我们不用那样,只要心里举几个例子,验证下是否比它更好即可,如果举不出例子,那么就可以认为这就是最优解了。 虽然贪心算法虽然在大部分实践场景中都能得到最优解,但是并不能保证一定是最优解。比如在如下的有向带权图中寻找从S到T的最短路径,那么答案肯定就是S->A->E->T,总代价为1+4+4=9; 然而,实际上的最短路径是S->B->D->T,总代价为6。 所以,不能所有这类问题都迷信贪心算法的求解,但其作为一种算法指导思想,还是很值得学习的。 除了以上袋子装豆子的问题之外,还有很多应用场景。这种问题能否使用贪心算法来解决的关键是你能否将问题转换为贪心算法适用的问题,即找到问题的限制值和期望值。 我们有m个糖果要分给n个孩子,n大于m,注定有的孩子不能分到糖果。其中,每个糖果的大小都不同,分别为S1,S2,S3...,Sm,每个孩子对糖果的需求也是不同的,为N1,N2,N3...,Nn,那么我们如何分糖果,才能尽可能满足最多数量孩子的需求? 这个问题中,限制值是糖果的数量m,期望值满足最多的孩子需求。对于每个孩子,能用小的糖果满足其需求,就不要用大的,避免浪费。所以我们可以给所有孩子的需求排个序,从需求最小的孩子开始,用刚好能满足他的糖果来分给他,以此来分完所有的糖果。 我们有1元、5元、10元、20元、50元、100元纸币各C1、C5、C10、C20、C50、C100张,现在要购买一个价值K元的东西,请问怎么才能适用最少的纸币? 这个问题应该不难,限制值是各个纸币的张数,期望值是适用最少的纸币。那么我们就先用面值最大的100元去付钱,当再加一张100元就超过K时,就更换小面额的,直至正好为K元。 对于n个区间[L1,R1],[L2,R2]...[Ln,Rn],我们怎么从中选出尽可能多的区间,使它们不相交? 我们需要把这个问题转换为符合贪心算法特点的问题,假设这么多区间的最左端点是Lmin,最右端点是Rmax,那么问题就是在[Lmin,Rmax]中,选择尽可能多的区间往里面塞,并且保证它们不相交。这里,限制值就是区间[Lmin,Rmax],期望值就是尽可能多的区间。 我们的解决办法就是每次从区间中选择那种左端点>=已经覆盖区间右边端点的,且该区间右端点尽可能高小的。如此,我们可以让未覆盖区间尽可能地大,才能保证可以塞进去尽可能多的区间。 贪心算法最重要的就是学会如何将要解决的问题抽象成适合贪心算法特点的模型,找到限制条件和期望值,只要做好这一步,接下来的就比较简单了。在平时我们不用刻意去记,多多练习类似的问题才是最有效的学习方法。
2023-08-08 05:28:131

贪心算法的基本思路

1.建立数学模型来描述问题⒉把求解的问题分成若干个子问题。⒊对每一子问题求解,得到子问题的局部最优解。⒋把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程:从问题的某一初始解出发;while 能朝给定总目标前进一步do求出可行解的一个解元素;由所有解元素组合成问题的一个可行解。下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
2023-08-08 05:28:221

贪心算法的特性

贪婪算法可解决的问题通常大部分都有如下的特性:⑴随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。⑵有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。⑶还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。⑷选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。⑸最后,目标函数给出解的值。⑹为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。
2023-08-08 05:28:371

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

u2022贪心算法的特点是每个阶段所作的选择都是局部最优的,它期望通过所作的局部最优选择产生出一个全局最优解。 贪心与动态规划: 与动态规划不同的是,贪心是 鼠目寸光 ;动态规划是 统揽全局 。 –动态规划:每个阶段产生的都是全局最优解 u2022第i阶段的“全局”: 问题空间为(a1, … , ai) u2022第i阶段的“全局最优解”:问题空间为 (a1, … , ai)时的最优解 –贪心:每个阶段产生的都是局部最优解 u2022第i阶段的“局部”:问题空间为按照贪心策略中的优先级排好序的第i个输入ai u2022第i阶段的“局部最优解”: ai u2022贪心选择性质:所求问题的全局最优解可以通过一系列局部最优的选择(即贪心选择)来达到。 –这是贪心算法与动态规划算法的主要区别。 u2022最优子结构性质:当原问题的最优解包含子问题的最优解时,称此问题具有最优子结构性质。 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征 u2022要求高效地安排一系列争用某一公共资源(例如会议室)的活动(使尽可能多的活动能兼容使用公共资源)。 –设有n个活动的集合E={e1,e2…en},其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。 –若区间[si,fi)与区间[sj,fj)不相交,则称ei和ej是相容的。也就是说,当si≥fj或sj≥fi时,活动i和活动j相容。 u2022活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
2023-08-08 05:28:511

Pascal贪心算法,求解答!

这道题用贪心不大好吧记得老师以前说过这种题用DP这道题是最简单的01背包我给你发个资料那个,发不了啊,上传失败你给我qq吧P01: 01背包问题题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 注意f[i][v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[i][v-1],这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以,由你自己来体会了。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f [0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。伪代码如下: for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。 总结 01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。 P02: 完全背包问题 题目 有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路 这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}。这跟01背包问题一样有O(N*V)个状态需要求解,但求解每个状态的时间则不是常数了,求解状态f[i][v]的时间是O(v/c[i]),总的复杂度是超过O(VN)的。 将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。 一个简单有效的优化 完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。 转化为01背包问题求解 既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c [i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。 更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c[i]))件物品,是一个很大的改进。 但我们有更优的O(VN)的算法。 * O(VN)的算法 这个算法使用一维数组,先看伪代码: <pre class"example"> for i=1..N for v=0..Vf[v]=max{f[v],f[v-c[i]]+w[i]}; 你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。 这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等价地变形成这种形式:f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]},将这个方程用一维数组实现,便得到了上面的伪代码。 总结 完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。 P03: 多重背包问题 题目 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则:f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}。复杂度是O(V*∑n[i])。 转化为01背包问题 另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i]件01背包中的物品,则得到了物品数为∑n[i]的01背包问题,直接求解,复杂度仍然是O(V*∑n[i])。 但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想,我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外,取超过n[i]件的策略必不能出现。 方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。 分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示,这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出,并不难,希望你自己思考尝试一下。 这样就将第i种物品分成了O(log n[i])种物品,将原问题转化为了复杂度为O(V*∑logn[i])的01背包问题,是很大的改进。 O(VN)的算法 多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程,但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围,故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。 小结 这里我们看到了将一个算法的复杂度由O(V*∑n[i])改进到O(V*∑log n[i])的过程,还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法,自己证明一下它的正确性,并用尽量简洁的程序来实现。 P04: 混合三种背包问题 问题 如果将P01、P02、P03混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢? 01背包与完全背包的混合 考虑到在P01和P02中最后给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类物品可以取无限次,那么只需在对每个物品应用转移方程时,根据物品的类别选用顺序或逆序的循环即可,复杂度是O(VN)。伪代码如下: for i=1..N if 第i件物品是01背包 for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; else if 第i件物品是完全背包 for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]}; 再加上多重背包 如果再加上有的物品最多可以取有限次,那么原则上也可以给出O(VN)的解法:遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话,用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。 小结 有人说,困难的题目都是由简单的题目叠加而来的。这句话是否公理暂且存之不论,但它在本讲中已经得到了充分的体现。本来01背包、完全背包、多重背包都不是什么难题,但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实,领会三种基本背包问题的思想,就可以做到把困难的题目拆分成简单的题目来解决。 P05: 二维费用的背包问题 问题 二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。 算法 费用加了一维,只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。状态转移方程就是:f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量v和u采用顺序的循环,当物品有如完全背包问题时采用逆序的循环。当物品有如多重背包问题时拆分物品。 物品总个数的限制 有时,“二维费用”的条件是以这样一种隐含的方式给出的:最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用,每个物品的件数费用均为1,可以付出的最大件数费用为M。换句话说,设f[v][m]表示付出费用v、最多选m件时可得到的最大价值,则根据物品的类型(01、完全、多重)用不同的方法循环更新,最后在f[0..V][0..M]范围内寻找答案。 另外,如果要求“恰取M件物品”,则在f[0..V][M]范围内寻找答案。 小结 事实上,当发现由熟悉的动态规划题目变形得来的题目时,在原来的状态中加一纬以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。 P06: 分组的背包问题 问题 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 算法 这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i属于第k组}。 使用一维数组的伪代码如下: for 所有的组k for 所有的i属于组k for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]} 另外,显然可以对每组中的物品应用P02中“一个简单有效的优化”。 小结 分组的背包问题将彼此互斥的若干物品称为一个组,这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题(例如P07),由分组的背包问题进一步可定义“泛化物品”的概念,十分有利于解题。 P07: 有依赖的背包问题 简化的问题 这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。 算法 这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。 按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择一个附件,选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。(事实上,设有n个附件,则策略有2^n+1个,为指数级。) 考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略),所以一个主件和它的附件集合实际上对应于P06中的一个物品组,每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法,因为物品组中的物品还是像原问题的策略一样多。 再考虑P06中的一句话: 可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们,对于一个物品组中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,我们可以对主件i的“附件集合”先进行一次01背包,得到费用依次为0..V-c[i]所有这些值时相应的最大价值f"[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组,其中费用为c[i]+k的物品的价值为f"[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的,通过一次01背包后,将主件i转化为 V-c[i]+1个物品的物品组,就可以直接应用P06的算法解决问题了。 更一般的问题 更一般的问题是:依赖关系以图论中“森林”的形式给出(森林即多叉树的集合),也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。 解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是,由于附件可能还有附件,就不能将每个附件都看作一个一般的01 背包中的物品了。若这个附件也有附件集合,则它必定要被先转化为物品组,然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。 事实上,这是一种树形DP,其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后,你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。 小结 NOIP2006的那道背包问题我做得很失败,写了上百行的代码,却一分未得。后来我通过思考发现通过引入“物品组”和“依赖”的概念可以加深对这题的理解,还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系:物品不能既作主件又作附件,每个主件最多有两个附件,可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组,这便揭示了问题的某种本质。 我想说:失败不是什么丢人的事情,从失败中全无收获才是。 P08: 泛化物品 定义 考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。 更严格的定义之。在背包容量为V的背包问题中,泛化物品是一个定义域为0..V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。 这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组h[0..V],给它费用v,可得到价值h[V]。 一个费用为c价值为w的物品,如果它是01背包中的物品,那么把它看成泛化物品,它就是除了h(c)=w其它函数值都为0的一个函数。如果它是完全背包中的物品,那么它可以看成这样一个函数,仅当v被c整除时有h(v)=v/c*w,其它函数值均为0。如果它是多重背包中重复次数最多为n的物品,那么它对应的泛化物品的函数有h(v)=v/c*w仅当v被c整除且v/c<=n,其它情况函数值均为0。 一个物品组可以看作一个泛化物品h。对于一个0..V中的v,若物品组中不存在费用为v的的物品,则h(v)=0,否则h(v)为所有费用为v的物品的最大价值。P07中每个主件及其附件集合等价于一个物品组,自然也可看作一个泛化物品。 泛化物品的和 如果面对两个泛化物品h和l,要用给定的费用从这两个泛化物品中得到最大的价值,怎么求呢?事实上,对于一个给定的费用v,只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的,对于0..V的每一个整数v,可以求得费用v分配到h和l中的最大价值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到,f也是一个由泛化物品h和l决定的定义域为0..V的函数,也就是说,f是一个由泛化物品h和 l决定的泛化物品。 由此可以定义泛化物品的和:h、l都是泛化物品,若泛化物品f满足f(v)=max{h(k)+l(v-k)|0<=k<=v},则称f是h与l的和,即f=h+l。这个运算的时间复杂度是O(V^2)。 泛化物品的定义表明:在一个背包问题中,若将两个泛化物品代以它们的和,不影响问题的答案。事实上,对于其中的物品都是泛化物品的背包问题,求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为s,则答案就是s[0..V]中的最大值。 背包问题的泛化物品 一个背包问题中,可能会给出很多条件,包括每种物品的费用、价值等属性,物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说,给定了所有条件以后,就可以对每个非负整数v求得:若背包容量为v,将物品装入背包可得到的最大价值是多少,这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品——或者说问题所对应的一个定义域为非负整数的函数——包含了关于问题本身的高度浓缩的信息。一般而言,求得这个泛化物品的一个子域(例如0..V)的值之后,就可以根据这个函数的取值得到背包问题的最终答案。 综上所述,一般而言,求解背包问题,即求解这个问题所对应的一个函数,即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。 小结 本讲可以说都是我自己的原创思想。具体来说,是我在学习函数式编程的 Scheme 语言时,用函数编程的眼光审视各类背包问题得出的理论。这一讲真的很抽象,也许在“模型的抽象程度”这一方面已经超出了NOIP的要求,所以暂且看不懂也没关系。相信随着你的OI之路逐渐延伸,有一天你会理解的。 我想说:“思考”是一个OIer最重要的品质。简单的问题,深入思考以后,也能发现更多。 P09: 背包问题问法的变化 以上涉及的各种背包问题都是要求在背包容量(费用)的限制下求可以取到的最大价值,但背包问题还有很多种灵活的问法,在这里值得提一下。但是我认为,只要深入理解了求背包问题最大价值的方法,即使问法变化了,也是不难想出算法的。 例如,求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值(f数组)之后得到。 还有,如果要求的是“总价值最小”“总件数最小”,只需简单的将上面的状态转移方程中的max改成min即可。
2023-08-08 05:28:581

动态规划和贪心算法的区别

如下:贪心法是每一步的最优解就是整体的最优解。0-1背包是属于动态规划,每一步的解不一定导致整体的最优解。对于你问“什么样的题用0-1背包问题作”就是需要你自己做题来体会了。如果全局的最优解可以用分布的最优解求出来,就用贪心,如果不是,就动态规划(0-1背包属于这类)。合并果子问题(可以自己去网上找哈~)就是典型的贪心,0-1背包问题就属于典型动态规划。贪心算法特性:贪心算法的关键不在于想到,而在于正确性的证明。要证明一个贪心算法是正确的,需要证明我们可以把一个最优解逐步转化为我们用贪心算法所得到的解。而解不会更差,从而证明贪心算法得到的解和最优解是一样好的(显然,最优解不可能更好)。而要证明一个贪心算法是错误的,只需要找到一个反例就可以了。动态规划和贪心算法都是一种递推算法,均有局部最优解来推导全局最优解,贪心算法:动态规划算法:贪心算法与动态规划。每次拿能拿的最大的,就是贪心。但是一定注意,贪心得到的并不是最优解,也就是说用贪心不一定是拿的最少的张数。
2023-08-08 05:29:131

没有使用贪心策略的算法

KMP算法。KMP算法是一种改进的字符串匹配算法。为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀,在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next[j]=-1,则将i右移1位,并将j置0,继续进行比较。贪心算法,又称贪婪算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
2023-08-08 05:29:271

[算法] 贪心算法证明思路

动态规划和贪心算法都需要问题具有最优子结构,但不同的是贪心 自顶向下 ,先做选择再求解一个结果子问题,而动态规划自底向上求解子问题,需要先求出子问题的最优解再做选择。这是因为,动态规划最优解有两个子问题时,求解子问题 时有j-i-1种选择,但贪心选择特征能够使 其中一个子问题必定为空 ,这种子问题和选择数目的减少使得子问题能够自顶向下被解决。 a) 定义子问题空间,做出一个选择从而产生一个或多个子问题。子问题空间的定义结合需要求解的目标和选择后子问题的描述刻画来考虑。 b) 利用“剪切-粘贴”证明作为最优解的组成部分的每个子问题的解也是它本身的最优解。如果子问题的解不是最优解,将其替换为对应的最优解从而一定能得到原问题一个更优的解,这与最初的解是原问题的最优解的前提假设矛盾,因此最优子结构得证。 贪心的本质是局部最优解能产生全局最优解,即产生两个子问题 和 时,可以直接解决子问题 (在子问题 中,使用贪心策略选择a作为局部最优解)然后对子问题 进行分解,最终可以合并为全局最优解。 因此,要证明贪心选择性质只需要证明 存在一个最优解是通过当前贪心选择策略得到的 ,反过来,即证明**通过非贪心策略得到的原问题的最优解中也一定包含局部最优解a。 定义通过非贪心策略的选择可以得到的一个最优解A,将最优解中的元素和当前贪心策略会选择的元素逐个交换后得到的解A"并不比 A差(假设贪心策略会选择的元素在当前最优解中未被选择,通过“剪切-粘贴”证明得到的仍是最优解),可以证明存在原问题的最优解可以通过贪心选择得到。
2023-08-08 05:29:511

C语言,贪心算法,货币找零问题?

#include <stdio.h>int main(){ int m,n,i; int a[6]={50,20,10,5,2,1}; n=0; printf("请输入找零总数: "); scanf("%d",&m); for(i=0;i<6;i++) { n=n+m/a[i]; m=m%a[i]; } printf("%d",n);}
2023-08-08 05:30:012

程序员都应该精通的六种算法,你会了吗?

对于一名优秀的程序员来说,面对一个项目的需求的时候,一定会在脑海里浮现出最适合解决这个问题的方法是什么,选对了算法,就会起到事半功倍的效果,反之,则可能会使程序运行效率低下,还容易出bug。因此,熟悉掌握常用的算法,是对于一个优秀程序员最基本的要求。 那么,常用的算法都有哪些呢?一般来讲,在我们日常工作中涉及到的算法,通常分为以下几个类型:分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。 一、分治算法 分治算法,顾名思义,是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治算法一般分为三个部分:分解问题、解决问题、合并解。 分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立,求出来的解可以合并为该问题的解的情况。 典型例子比如求解一个无序数组中的最大值,即可以采用分治算法,示例如下: def pidAndConquer(arr,leftIndex,rightIndex): if(rightIndex==leftIndex+1 || rightIndex==leftIndex){ return Math.max(arr[leftIndex],arr[rightIndex]); } int mid=(leftIndex+rightIndex)/2; int leftMax=pidAndConquer(arr,leftIndex,mid); int rightMax=pidAndConquer(arr,mid,rightIndex); return Math.max(leftMax,rightMax); 二、贪心算法 贪心算法是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。 贪心算法的基本思路是把问题分成若干个子问题,然后对每个子问题求解,得到子问题的局部最优解,最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少,更大的用途在于平衡算法效率和最终结果应用,类似于:反正就走这么多步,肯定给你一个值,至于是不是最优的,那我就管不了了。就好像去菜市场买几样菜,可以经过反复比价之后再买,或者是看到有卖的不管三七二十一先买了,总之最终结果是菜能买回来,但搞不好多花了几块钱。 典型例子比如部分背包问题:有n个物体,第i个物体的重量为Wi,价值为Vi,在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分,价值和重量按比例计算。 贪心策略就是,每次都先拿性价比高的,判断不超过C。 三、迭代算法 迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法,它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。最终得到问题的结果。 迭代算法适用于那些每步输入参数变量一定,前值可以作为下一步输入参数的问题。 典型例子比如说,用迭代算法计算斐波那契数列。 四、枚举算法 枚举算法是我们在日常中使用到的最多的一个算法,它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。 枚举算法适用于候选答案数量一定的情况。 典型例子包括鸡钱问题,有公鸡5,母鸡3,三小鸡1,求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下: 五、回溯算法 回溯算法是一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。 许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。 典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问一共有多少种摆法。 回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置,那么下一个皇后的位置便被限制住了,下一个皇后需要一直找直到找到安全位置,如果没有找到,那么便要回溯到上一个皇后,那么上一个皇后的位置就要改变,这样一直递归直到所有的情况都被举出。 六、动态规划算法 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 动态规划算法适用于当某阶段状态给定以后,在这阶段以后的过程的发展不受这段以前各段状态的影响,即无后效性的问题。 典型例子比如说背包问题,给定背包容量及物品重量和价值,要求背包装的物品价值最大。
2023-08-08 05:30:141

大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系?

对于,大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题,首先要来聊聊他们的联系:1、都是一种推导算法;2、将它们分解为子问题求解,它们都需要有最优子结构。这两个特征师门的联系。然后,下面来说说他们的差别:贪心算法需要每一步的最优解必须包含前一步的最优解,前一步的最优解不保留;而动态规划是全局最优解必须包含一个局部最优解,而不是先前的局部最优解。因此,有必要记录所有以前的局部最优解。另一个不同是,贪心算法它如果所有子问题都被视为一棵树,贪婪从根开始,每次都遍历最优子树(通常这种“最优”基于当前情况下明显的“最优”);这样,就不需要知道一个节点的所有子树,所以它不能形成一个完整的树;而动态规划是从下到上,从叶到根构造子问题的解决方案。对于每个子树的根,找到下面每个叶子的值。最后,得到一棵完整的树,最后选择最优值作为自己的值来得到答案。可见,根据以上描述,贪心算法不能保证最终的解决方案是最好的,总体复杂度较低;动态规划的本质是穷举法,它能保证最优的结果和较高的复杂性。特别是对于0-1背包问题,它应该比较选择项目和不选择项目所导致的最终方案,然后做出最佳选择。由此衍生出许多重叠子问题,因此使用了动态规划。拓展资料:贪婪算法是指在解决问题时,它总是在当前做出最佳选择。也就是说,在不考虑全局优化的情况下,该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。动态规划是运筹学的一个分支,是解决决策过程优化的过程。20世纪50年代初,美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时,提出了著名的最优化原理,建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用,在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显著的成果。
2023-08-08 05:30:211

动态规划和贪心算法的区别

动态规划和贪心算法的区别1、动态规划算法中,每步所做的选择往往依赖于相关子问题的解,因而只有在解出相关子问题时才能做出选择。而贪心算法,仅在当前状态下做出最好选择,即局部最优选择,然后再去解做出这个选择后产生的相应的子问题。2、动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常自顶向下的方式进行。共同点:两者都具有最优子结构性质 动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。
2023-08-08 05:32:051

贪心算法 部分背包问题

  [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。  要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。  物品 A B C D E F G   重量 35 30 60 50 40 10 25   价值 10 40 30 50 35 40 30   分析:  目标函数: ∑pi最大  约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)  (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?  (2)每次挑选所占重量最小的物品装入是否能得到最优解?  (3)每次选取单位重量价值最大的物品,成为解本题的策略。 ?  值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。  贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。  可惜的是,它需要证明后才能真正运用到题目的算法中。  一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。  对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:  (1)贪心策略:选取价值最大者。反例:  W=30  物品:A B C  重量:28 12 12  价值:30 20 20  根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。  (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。  (3)贪心策略:选取单位重量价值最大的物品。反例:  W=30  物品:A B C  重量:28 20 10  价值:28 20 10  根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
2023-08-08 05:32:251

贪心算法 如何解答三值排序问题 [IOI 1996]

题解(from USACO)三值排序问题 [IOI 1996]有一个由N个数值均为1、2或3的数构成的序列(N<= 1000),其值无序,现要求你用最少的交换次数将序列按升序顺序排列。算法:排序后的序列分为三个部分:排序后应存储1的部分,排序后应存储2的部分和排序后应存储3的部分,贪心排序法应交换尽量多的交换后位置正确的(2,1)、(3,1)和(3,2)数对。当这些数对交换完毕后,再交换进行两次交换后位置正确的(1,2,3)三个数。 分析:很明显,每一次交换都可以改变两个数的位置,若经过一次交换以后,两个数的位置都由错误变为了正确,那么它必定最优。同时我们还可发现,经过两次交换后,我们可以随意改变3个数的位置。那么如果存在三个数恰好为1,2和3,且位置都是错误的,那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质,我们的贪心算法成立程序:var a:array[1..1000] of integer; f:array[1..3,1..3] of integer; b:array[1..3] of integer; n,i,j,t,p:integer;begin readln(n); for i:=1 to n do readln(a[i]); fillchar(f,sizeof(f),0); for i:=1 to n do inc(b[a[i]]); b[2]:=b[2]+b[1]; b[3]:=n; t:=0; for i:=1 to n do if i<=b[1] then inc(f[1,a[i]]) else if i<=b[2] then inc(f[2,a[i]]) else if i<=b[3] then inc(f[3,a[i]]); for i:=1 to 2 do for j:=i+1 to 3 do begin if f[i,j]>f[j,i] then p:=f[j,i] else p:=f[i,j]; t:=t+p; if f[i,j]-p>=0 then f[i,j]:=f[i,j]-p; if f[j,i]-p>=0 then f[j,i]:=f[j,i]-p; end; t:=t+(f[1,2]+f[1,3]) shl 1; writeln(t);end.另外,站长团上有产品团购,便宜有保证
2023-08-08 05:32:321

贪心算法 活动安排问题

先按结束时间从小到大排序,然后遍历一遍,能安排就安排就行了
2023-08-08 05:32:412

迪杰斯特拉算法的本质是贪心还是动态规划?

一般意义上的贪心算法在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。Dijkstra算法显然是从整体最优考虑,求出的最短路径,一定是整体最优解,这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性:待求解的问题分解为若干个子问题,前一子问题的解,为后一子问题的求解提供了有用的信息。在我看来,Dijkstra算法更接近动态规划。从维基百科也可以看到这样的说明:From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.
2023-08-08 05:32:492

为什么贪心算法不能解0-1背包问题

因为贪心算法的正确性无法被证明,而且有反例
2023-08-08 05:33:152

贪心算法是如何解决问题?

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性:1、随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后,目标函数给出解的值。
2023-08-08 05:33:341

贪心算法的基本思想是什么?

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性:1、随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后,目标函数给出解的值。
2023-08-08 05:33:561

贪心算法的基本思想是什么?

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性:1、随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后,目标函数给出解的值。
2023-08-08 05:34:191

什么是贪心算法?

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行,根据某个优化测度(可能是目标函数,也可能不是目标函数),每一步上都要保证能获得局部最优解。每一步只考虑一个数据,它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性:1、随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后,目标函数给出解的值。
2023-08-08 05:34:391

贪心算法是什么

很形象的说贪心算法,只注重当前利益最大化,即选择当前步骤的最优解。
2023-08-08 05:35:013

贪心算法的介绍

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
2023-08-08 05:35:231

贪心算法是什么

是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部 最优解。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
2023-08-08 05:35:361

贪心算法的基本要素是?

从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
2023-08-08 05:35:462

贪心算法基本要素有()和最优子结构性质。

贪心算法基本要素有()和最优子结构性质。 A.分解合并性质 B.独立子问题性质 C.贪心选择性质 D.重叠子问题性质 正确答案:C
2023-08-08 05:35:531

简述贪心,递归,动态规划,及分治算法之间的区别和联系

递归,简单的重复,计算量大。分治,解决问题独立,分开计算,如其名。动态规划算法通常以自底向上的方式解各子问题,贪心算法则通常以自顶向下的方式进行;动态规划能求出问题的最优解,贪心不能保证求出问题的最优解
2023-08-08 05:36:142

将最优装载问题的贪心算法推广到2艘船的情形,贪心算法仍能产生最优解吗?

不能...见主教材的转载问题
2023-08-08 05:36:293

采用贪心算法保证能求得最优解的问题是(  )。

【答案】:D贪心法在一般情况下一定能够得到满意解,不一定能够得到最优解。贪心法能够获得最优解的前提是:(1)问题具有最优子结构,即规模为n的问题的最优解与规模为n-1的问题的解相关;(2)问题具有贪心选择性质,即问题的整体最优解可以通过一系列局部最优的选择得到。部分背包问题具有以上性质,故可以通过贪心算法得到最优解。
2023-08-08 05:36:431

教材中给出了遍历算法策略和贪心算法策略,为什么遍历不可行而贪心算法可行,二者求得的结果一样吗

遍历算法是一种暴力搜索方法,它会枚举所有可能的解,然后从中选取最优解。但是,当问题规模非常大时,遍历算法的时间复杂度会非常高,计算时间过长,效率低下,甚至无法得到结果。因此,在这种情况下,采用贪心算法可以更加高效地解决问题。贪心算法是一种每一步都选择当前最优解的策略,从而得到全局最优解的方法。它通常比遍历算法更加高效,因为它只需要考虑当前步骤的最优解,而不需要考虑所有可能的解。因此,贪心算法的时间复杂度相对较低,计算速度较快。虽然贪心算法和遍历算法可能会得到相同的结果,但是在问题规模非常大的情况下,贪心算法更加实用。同时,需要注意的是,贪心算法得到的结果不一定是全局最优解,而可能只是局部最优解。
2023-08-08 05:36:501

C语言关于贪心算法的(很简单)

longa,b,s,k,num,c[7]={100,50,20,10,5,2,1}//a,顾客付款;b,实际售价;num找钱数。for(s=a-b,k=0,num=0;k<7&&s>0;k++){num+=(long)s/c[k];s-=num*c[k];}printf("%d",num);//k可以不要
2023-08-08 05:36:582