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

第1题：

第2题：

请叙述动态规划算法与贪心算法的异同。

正确答案: 共同点：
都需要最优子结构性质，
都用来求有优化问题。
不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；
贪心方法：自顶向下求解。
可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。

第3题：

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

正确答案:按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。

第4题：

贪心算法的基本要素是（）质和（）性质。

正确答案:贪心选择；最优子结构

第5题：

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

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

正确答案:B

第6题：

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

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

正确答案:D

第7题：

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

正确答案:最好；局部最优选择

第8题：

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

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

正确答案:A

第9题：

第10题：

第11题：

第12题：

第13题：

（）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

正确答案:贪心选择性质

第14题：

对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

• A、0－1背包问题和背包问题都可用贪心算法求解
• B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
• C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
• D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

正确答案:C

第15题：

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

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

正确答案:C

第16题：

大整数乘法算法是（）算法。

• A、分治
• B、贪心
• C、动态规划
• D、穷举

正确答案:A

第17题：

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

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

正确答案:B

第18题：

贪心算法算法的基本要素是（）、（）。

正确答案:最优子结构；贪心选择

第19题：

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

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

正确答案:C

第20题：

第21题：

第22题：

第23题：