从-1开始学贪心——贪心算法学习笔记

题库

原理

Johnson法则

物品i与j在A和B台机器上加工，只能先被机器A加工后被机器B加工。记物品k在A机器加工须用时a_k，在B机器加工须用时b_k。证明：当物品i,j满足 \(min{a_i,b_j} 时，先加工i可以得到最优解。
证明：
假设有2台机器A和B，有2件物品i和j，加工完成物品所需时间为T(i,j) 易知加工总时间t=t(B在加工）+t(B在休息)，则因为先加工i可以使所需时间更短，所以先加工i时，B机器的等待时间更少。
则 \(a_i+max{0,a_j-b_i}
移项得 $max{0,a_j-b_i}-max{0,a_i-b_j} 提出主要项得 \(（a_j+max{-a_j,-b_i})-(a_i+max{-a_i,-b_j})
也即 \(max{-a_j,-b_i}-max{-a_i,-b_j}<0\)
提出负号，再移项得 \(min{a_i,b_j}
即当物品i,j满足 \(min{a_i,b_j} 时，先加工i可以得到最优解。
Q.E.D.

上文中\(min{a_i,b_j}为Johnson法则的数学表达式，这种论证方法即为交换论证。

参考文章

1. 从零开始学贪心算法