算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？

参考答案：A

正确答案：B

参考答案：B

正确答案：C

正确答案：B
解析：对于具有最优子结构和重叠子问题的问题，可以用动态规划求解问题，求解过程中通常需要建立最优子结构的递归关系。分治算法的基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。回溯算法也称为试探算法，该算法首先放弃关于问题规模大小的限制，并将问题的候选解按某种次序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解，若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。用回溯算法找解的算法常常被编写成递归函数。贪心算法是一种不追求最优解，而是希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费大量的时间。贪心法不要回溯。因此贪心算法策略与递归技术的联系最弱。

参考答案：A

正确答案：B
解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。

参考答案：B

正确答案：A
解析：贪心算法是一种不追求最优解，而是希望得到较为满意解的算法。该算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费大量的时间。由于贪心法不要回溯，因此贪心算法策略与递归技术的联系最弱。回溯算法也称为试探算法，该算法首先放弃关于问题规模大小的限制，并将问题的候选解按某种次序逐一枚举和检验。当发现当前候选解不可能是解时，就选自择下一个候选解，若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。用回溯算法找解的算法常常被编写成递归函数。分治算法的基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。对于具有最优子结构和重叠子问题的问题，可以用动态规划求解问题，求解过程中通常需要建立最优子结构的递归关系。

正确答案：C
同上一题解析