经典贪心：最大延时最小问题

问题描述
贪心方法试探
短作业优先的尝试证明
短作业优先的构*例研究
从反例不等式组推正确的贪心方法
期限早优先法的证明

问题描述

经典贪心：最大延时最小问题

贪心方法试探

首先可以想到一些贪心方法，比如按执行时间排序做短作业优先的过程。我们分析它行不行，即尝试证明这种方法。

短作业优先的尝试证明

假设求出的处理序列有相邻两项 $project_i$ 和 $project_{i+1}$ ，按照约定， $t_i<t_{i+1}$ 。这两项交换不会影响其他项，所以只考虑这两项对自己的影响：
原来的延时二元组是 $(sum+t_i-d_i ,\quad sum+t_{i}+t_{i+1}-d_{i+1})$
交换后的延时二元组是 $(sum+t_{i+1}-d_{i+1} ,\quad sum+t_i+t_{i+1}-d_i)$
其中 $sum=\sum_{k=1}^{i-1}t_k$
但是每个数都加了sum，因为只研究大小关系，sum早晚会消掉，可以忽略。
那么能否证明 $max(t_i-d_i ,\quad t_{i}+t_{i+1}-d_{i+1}) \leqslant max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i)$
从而证明这种贪心的正确性呢？
很不幸，不能。可以想办法构*例。

短作业优先的构*例研究

如果能够造两个项目满足下面不等式组 $\left\{ \begin{array}{l} t_{i}+t_{i+1}-d_{i+1} \geqslant t_i-d_i\\\\ t_i+t_{i+1}-d_i \leqslant t_{i+1}-d_{i+1}\\\\ t_i \leqslant t_{i+1}(约定条件)\\\\ t_{i}+t_{i+1}-d_{i+1} \geqslant t_{i+1}-d_{i+1}(t_i非负自然满足) \end{array} \right.$
的话，那原来的答案延时 $t_{i}+t_{i+1}-d_{i+1}$ 就会变成 $t_{i+1}-d_{i+1}$ ,从而变小。这样这种短作业优先的方法就不是最优的。
比如t1=1,d1=100,t2=2,d2=2这个样例就满足上面的不等式组，从而形成反例。

从反例不等式组推正确的贪心方法

如何让上面的反例不等式组无论如何也不可能满足呢?很自然发现只要保证 $d_i<d_{i+1}$ 就行。

期限早优先法的证明

通过上面的推算已经能猜出这种改进方法八九不离十是对的，即按这种办法排序后，交换两项后答案不可能变小。
同样考虑相邻两项：
即能否证明 $max(t_i-d_i ,\quad t_{i}+t_{i+1}-d_{i+1}) \leqslant max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i)\\when \quad d_i \leqslant d_{i+1}$
显然是可以的，因为此时一定存在
$\left\{ \begin{array}{l} t_i+t_{i+1}-d_i \geqslant t_i-d_i\\\\ t_i+t_{i+1}-d_i \geqslant t_{i}+t_{i+1}-d_{i+1}\\\\ max(t_{i+1}-d_{i+1} ,\quad t_i+t_{i+1}-d_i) \geqslant t_i+t_{i+1}-d_i \end{array} \right.$
所以交换一定不会让答案变小。
而且任何不安这种贪心的顺序的序列都能一步一步相邻两个符合次序的相邻对交换为逆序相邻对得到，就像冒泡排序。所以答案会随着这样的交换一点点变大。所以这种期限早优先法是对的。
这就是证明过程。

秒客网

经典贪心：最大延时最小问题