贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。基本思路是从问题的某…
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解，不回溯修改之前的决策。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。 根据上述定义，下列属于贪心算法的是：
A. 16枚硬币中有1枚重量较轻的伪造硬币，为找出这枚伪造的硬币，将所有硬币分为8组，每组两两进行重量比较，重量较轻的硬币即为伪造硬币B. 在国际象棋上摆放8个皇后，先放置1个皇后，如果下一个皇后没有符合要求的位置，就要回溯改变前一个皇后的位置，直到找到符合要求的所有位置C. 拥有硬币的面额有25分、10分、5分和1分，用尽可能少的硬币凑够37分，第一步先选最大面额25分，再选择剩余最大面额10分，最后选2枚1分的硬币D. 将无序的整体支票拆分到每份只有一张，将其两两合并且保证每组合并后均有序，一直两两合并直到重新得到整体，此时所有的支票就排好序了先想一想，再看答案与解析 ▸
正确答案：C
【正确率 73%｜考点：常规问法】
第一步：找出定义关键词。
贪心算法：“每一步都要确保能获得局部最优解”、“不回溯修改之前的决策”；
分治算法：“将一个问题分解为规模较小的子问题”、“求出子问题的解，得到原问题的解”。
第二步：逐一分析选项。
A项：将16枚硬币分为8组，每组两两进行重量比较，重量较轻的硬币即为伪造硬币，是根据分解后每组的结果来找到伪造的硬币，符合“将一个问题分解为规模较小的子问题”、“求出子问题的解，得到原问题的解”，符合“分治算法”定义，不符合“贪心算法”定义，排除；
B项：在国际象棋上摆放8个皇后，先放置1个皇后，如果下一个皇后没有符合要求的位置，就要回溯改变前一个皇后的位置，说明过程中需要不断回溯，不符合“不回溯修改之前的决策”，不符合“贪心算法”定义，排除；
C项：用尽可能少的硬币凑够37分，第一步先选一个最大面额25分的硬币，说明在37分的范围内选择最大的一个数去找零，是第一步的最优解；此时剩余12分，再选择最大面额10分的硬币，这是第二步的最优解；最后只剩2分，选2枚1分的硬币即可，符合“每一步都要确保能获得局部最优解”、“不回溯修改之前的决策”，符合“贪心算法”定义，当选；
D项：将无序的整体支票拆分到每份一张，将其两两合并且保证每组合并后均有序，一直合并到重新得到整体，这是将原问题进行分解，从小问题开始解决，直到解决原问题，符合“将一个问题分解为规模较小的子问题”、“求出子问题的解，得到原问题的解”，符合“分治算法”定义，不符合“贪心算法”定义，排除。
故正确答案为C。
考点常规问法