虽然动态规划法和贪心法都要求问题本身具有最优子结构特性,但动态规划法中,可以用子问题的解构造原问题的解,而贪心法中,却不可以用子问题的解构造原问题的最优解。
举一反三
- 动态规划法和贪心法都要求待求解的问题具备有_____________________。 A: 贪心选择性质 B: 重叠子问题 C: 最优子结构性质 D: 定义最优解
- 一个问题可用动态规划法或贪心法求解的关键特征是问题的是____ A: 贪心选择性质 B: 重叠子问题 C: 最优子结构性质 D: 定义最优解
- 有关分治法、贪心算法和动态规划算法的描述，正确的是（ ）。 A: 贪心算法和动态规划算法共同特征为最优子结构性质; B: 适用三种方法所解的问题都是可分解成子问题的； C: 问题能用动态规划法解的不一定能用贪心算法解； D: 用贪心法一定能用动态规划法，但是，动态规划法的效率一般高于贪心算法。
- 一个问题可用动态规划法或贪心算法求解的关键特征是问题具有____性质。 A: 重叠子问题 B: 最优子结构 C: 贪心选择 D: 定义最优解
- 贪心法与动态规划法的共同性质是 A: 子问题重叠 B: 子问题平衡独立 C: 最优子结构 D: 贪心选择