GESP-C++五级 题库
给定有 个任务,每个任务有截止时间和利润,每个任务耗时 1 个时间单位、必须在截止时间前完成,且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润,可以采用贪心策略,即按利润从高到低排序,尽量安排,则横线处应填写( )。
贪心算法的核心特征是?( )
贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。
假设有多个孩子,数组 g 保存所有孩子的胃口值。有多块饼干,数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干,每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时,孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子,因此打算采用贪心算法来找出能满足的孩子的数目,则横线上应填写的代码为( )。
贪心算法的核心思想是( )?
贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。
使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。
求解下图中A点到D点最短路径,其中A到B之间的12可以理解为距离。求解这样的问题常用Dijkstra算法,其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图(如距离不能为负值)单源最短路径的算法。

从该算法的描述可以看出,Dijkstra算法是贪心算法。( )
贪心算法通过每一步选择当前最优解,从而一定能获得全局最优解。( )
贪心算法是一种在每一步选择中都采取当前状态下最优(局部最优)的决策,从而希望导致全局最优解的算法策略,但是贪心算法 不一定能得到全局最优解。
贪心算法通过每一步选择局部最优解,从而一定能获得最优解。
贪心算法的使用条件是:局部最优能够得到全局最优,不是所有的问题都可以通过贪心实现,因为局部最优不一定能得到全局最优
贪心算法通过每一步选择局部最优解来获得全局最优解,但并不一定能找到最优解。
它通常在每一步做出局部最优选择,并希望通过这种方式最终达到全局最优解。然而,并不是所有问题都适合使用贪心算法,并且即使某些问题可以使用贪心算法,它也不能保证一定能找到全局最优解。