如果一个大问题可以被分解为若干个子问题,且子问题相互有重叠,求解此类问题较好的算法是()。
A: 贪心法
B: 分治法
C: 动态规划
D: 回溯法
A: 贪心法
B: 分治法
C: 动态规划
D: 回溯法
举一反三
- 把大问题分解成子问题,且子问题有大量重合的问题求解,较好的算法是()。 A: 贪心法 B: 分治法 C: 动态规划法 D: 回朔法
- 下面分治算法的说法正确的是() A: 分治法的设计思想是大事化小,各个击破,分而治之。 B: 每次都将问题分解为原问题规模的一半进行求解,称为二分法。 C: 分治法将原问题分解为若干个规模较小、相互独立、完全相同的子问题。 D: 减治法是把一个问题转化成一个子问题来解决。
- 用动态规划的前提条件( ) A: 能够分解为子问题,且子问题有重叠 B: 能够分解为相似子问题,且子问题有重叠 C: 能够分解为子问题 D: 递归问题都可以用动态规划求解
- 动态规划与贪心算法的最大区别( ) A: 贪心算法不是递归问题,动态规划是递归问题 B: 动态规划采用从下向上的方法求解,贪心算法采用从上向下的方法求解 C: 动态规划是子问题有重叠,贪心算法是局部最优能够得到全局最优 D: 一个问题能够用动态规划求解,就能够用贪心算法求解
- ()可以用于求解0-1背包问题。 A: 动态规划 B: 贪心算法 C: 分支限界法 D: 回溯法