动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，二者采用的都是自底向上的计算方式。

第1题：

第2题：

出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致（）。

正确答案:相同

第3题：

动态规划算法的基本思想是将待求解问题分解成若干（），先求解（），然后从这些（）的解得到原问题的解。

正确答案:子问题；子问题；子问题

第4题：

对于线性规划问题，已知原问题基本解不可行，对偶问题基本解可行，可采用对偶单纯形法求解。

正确答案:正确

第5题：

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

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

正确答案:B

第6题：

把大问题分解成子问题，且子问题有大量重合的问题求解，较好的算法是（）。

• A、贪心法
• B、分治法
• C、动态规划法
• D、回朔法

正确答案:C

第7题：

将一个较大规模的问题分解为较小规模的子问题，求解子问题、合并子问题的解得到整个问题的解的算法是（）。

• A、贪心法
• B、分治法
• C、动态规划法
• D、回朔法

正确答案:B

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

下列整数规划说明不正确的是（）。

• A、求解整数规划可以采用求解其相应的松驰问题，然后对其非整数值的解四舍五入的方法得到整数解
• B、用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常任取其中一个作为下界
• C、用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解
• D、用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数

正确答案:A,B,C

第14题：

使用分治法求解不需要满足的条件是（）。

• A、子问题必须是一样的
• B、子问题不能够重复
• C、子问题的解可以合并
• D、原问题和子问题使用相同的方法解

正确答案:A

第15题：

分支定界法在需要分支时必须满足：一是分支后的各子问题必须容易求解；二是各子问题解的集合必须覆盖原问题的解。

正确答案:正确

第16题：

分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）

• A、问题规模相同，问题性质相同
• B、问题规模相同，问题性质不同
• C、问题规模不同，问题性质相同
• D、问题规模不同，问题性质不同

正确答案:C

第17题：

动态规划算法有一个变形方法（）。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。

正确答案:备忘录方法

第18题：

在求解规模较大的问题时，可以把它分解成若干个规模较小的子问题，求出各个子问题的解之后，再把这些解合成原问题的解，这种方法是（）。

• A、穷举法
• B、回溯法
• C、分治法
• D、递归法

正确答案:C

第19题：

第20题：

第21题：

第22题：

第23题：

第24题：