6、贪心算法总是做出在当前看来（）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（局部最优选择)。

第1题：

第2题：

第3题：

第4题：

采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是（）。

• A、当前所作决策不会影响后面的决策
• B、原问题的最优解包含其子问题的最优解
• C、问题可以找到最优解，但利用贪心算法不能找到最优解
• D、每次决策必须是当前看来的最优决策才可以找到最优解

第5题：

下面是贪心算法的基本要素的是（）

• A、重叠子问题
• B、构造最优解
• C、贪心选择性质
• D、定义最优解

第6题：

贪心算法与动态规划算法的主要区别是（）。

• A、最优子结构
• B、贪心选择性质
• C、构造最优解
• D、定义最优解

第7题：

（）是贪心算法与动态规划算法的共同点。

• A、重叠子问题
• B、构造最优解
• C、贪心选择性质
• D、最优子结构性质

第8题：

动态规划算法的基本要素为（）

• A、最优子结构性质与贪心选择性质
• B、重叠子问题性质与贪心选择性质
• C、最优子结构性质与重叠子问题性质
• D、预排序与递归调用

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

正确答案：(6)能或可以、行及其他含义相同的词语 (7)不能或不可以、不行及其他含义相同的词语
(6)能，或可以、行及其他含义相同的词语 (7)不能，或不可以、不行及其他含义相同的词语 解析：本题考查的是算法的设计和分析技术。
问题1考查的是贪心算法的流程图。第(1)空表示第2个作业到第n个作业的主循环，i是循环控制变量，故第(1)空填入i<=n。
应注意到数组／中的作业J[i](1≤i≤k)是在其期限之前完成的作业，且d[J[i]]≤d[J[i+1]] (1≤id[i]。另一方面， J[D[R]]与r的关系只有两种：J[d[r]]>r，表示还可能在J[1]与J[r]之间插入作业i；J[d[r]]=r，表示不可能在J[1]～J[r]之间插入作业i。J[d[r]]问题2是本题算法的一个实例。6个作业的收益已经按降序排好序。根据流程图，将作业1，2，4和5放入数组J中，并得到总收益为220，具体过程如表4-1所示。

问题3考查算法策略。对于该题，贪心策略可以求得最优解。但不是所有的问题都能通过贪心策略来求得最优解，一个典型的例子是0-1背包问题。举例如下，有三件物品，背包可容纳50磅重的东西，每件物品的详细信息如表4-2所示，问如何装包使得其价值最大?

如果按贪心策略求解该问题，优先选择单位价值最大的物品，则先选择物品1，然后选择物品2。由于此时背包容量还剩下50-10-20=20，不足以容纳物品3，故总价值为 60+100=160美元。但若选择物品2和物品3，容量总和为20+30，小于等于总容量50，得到总价值为100+120=220，会得到更优解。此时用贪心策略不能得到最优解。

第15题：

贪心算法从初始阶段开始，每一个阶段总是作一个使（）的贪心选择。

第16题：

一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？

第17题：

贪心算法的基本要素是（）和最优子结构性质。

第18题：

一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。

• A、重叠子问题
• B、最优子结构性质
• C、贪心选择性质
• D、定义最优解

第19题：

贪心算法总是做出在当前看来（）的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的（）。

第20题：

能采用贪心算法求最优解的问题，一般具有的重要性质为：（）

• A、最优子结构性质与贪心选择性质
• B、重叠子问题性质与贪心选择性质
• C、最优子结构性质与重叠子问题性质
• D、预排序与递归调用

第21题：

第22题：

第23题：

第24题：