单选题：设有 $$n$$ 项作业，每个作业 $$j$$ 需要花费的处理时间为 $$t_j$$。我们将用局部搜索算法来吧作业分成两组 A

设有 $$n$$ 项作业，每个作业 $$j$$ 需要花费的处理时间为 $$t_j$$。我们将用局部搜索算法来吧作业分成两组 A 和 B，其中 A 组分配给机器 $$M_1$$，B 组分配给 $$M_2$$。在两台机器上处理全部作业所需要的时间为 $$T_1 = \sum_{j\in A} t_j$$ 和 $$T_2 = \sum_{j\in B} t_j$$。问题要求极小化 $$|T_1 - T_2|$$。

局部搜索：开始将作业 $$1, \ldots, n/2 $$ 分配给 $$M_1$$，其它的给 $$M_2$$。局部改进定义为将一个作业从一台机器转移到另一台。只有当这种转移能降低处理时间差的绝对值的时候，我们才做这种改进。下列哪句描述是正确的？ @[B](3)

A. 这是 NP 难问题，局部搜索不会终止。
B. 当有多个作业都可以被移动使得差的绝对值减小时，如果我们总是移动那个有最大 $$t_j$$ 的作业 $$j$$，则局部搜索至多进行 $$n$$ 步就终止。
C. 这种局部搜索算法总是能返回最优解。
D. 这种局部搜索算法总是能返回一个满足 $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$ 的局部解。




A.这是 NP 难问题，局部搜索不会终止。
B.当有多个作业都可以被移动使得差的绝对值减小时，如果我们总是移动那个有最大 $$t_j$$ 的作业 $$j$$，则局部搜索至多进行 $$n$$ 步就终止。
C.这种局部搜索算法总是能返回最优解。
D.这种局部搜索算法总是能返回一个满足 $$\frac{1}{2} T_1 \leq T_2 \leq 2 T_1$$ 的局部解。


答案：B