试题出自试卷《第五章 算法基础课后练习题（软设）【新版】》

问题1选项
A.分治
B.贪心
C.动态规划
D.回溯

问题2选项
A.动态规划
B.贪心
C.回溯
D.分支限界

第1题:C

第2题:D

第1题:

本题考查的是算法策略。

要想直接解决一个较大的问题，有时是相当困难的，分治法的设计思想是将一个难以解决的大问题分解成一些规模较小的相同问题，以便各个击破，分而治之。
动态规划法与分治法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，再从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。此时用一个中间表记录重复子问题的解，可以避免大量的重复计算。这就是动态规划法的基本思路。动态规划法的应用场景一般会出现“最优子结构”的描述，并且针对重复子问题的计算通过记录-查表，可以提高效率。本题第一空描述的是C选项动态规划法。
贪心法也经常用于解决最优化问题，与之不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，无论未来如何都不会改变。也就是只考虑当前最优，不考虑全局最优。一般不涉及划分和求解重复子问题。
回溯法可以系统地搜索一个问题的所有解或任意解。它在包含问题的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，但在一般情况下，分支限界法与回溯法的求解目标不同。分支限界法的求解目标是找出满足约束条件的一个解即可。由于求解目标不同，其探索方式与回溯法也不同，分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。本题第二空描述的是D选项分支限界法。

第2题: