若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且（a1，...

问答题若n=4，在机器M₁和M₂上加工作业i所需的时间分别为a_i和b_i，且（a₁，a₂，a₃，a₄）=（4，5，12，10），（b₁，b₂，b₃，b₄）=（8，2，15，9）求4个作业的最优调度方案，并计算最优值。

1.问答题写出设计动态规划算法的主要步骤。

①问题具有最优子结构性质；
②构造最优值的递归关系表达式；
③最优值的算法描述；
④构造最优解；

2.填空题二分搜索算法是利用（）实现的算法。

3.填空题动态规划算法的两个基本要素是（）和（）。

4.填空题0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。

O(n*2ⁿ)；O(min{nc,2ⁿ})

5.填空题以深度优先方式系统搜索问题解的算法称为（）。

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

7.填空题用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。

8.填空题若序列X={B，C，A，D，B，C，D}，Y={A，C，B，A，B，D，C，D}，请给出序列X和Y的一个最长公共子序列：（）

9.填空题某一问题可用动态规划算法求解的显著特征是（）。

10.填空题算法的复杂性有（）和（）之分，衡量一个算法好坏的标准是（）。