1、(1).贪心策略：按照加满油需要的时间从小到大对 C 中的汽车进行排序，得到一个新的
序列 ，按照此顺序进行加油得到的平均等待时间最短。
(2).
贪心选择性：
引理 1：要使得平均等待时间最短，则总的等待时间 T 也必须最短，故第一辆加油的汽车
对应的加油时间 必然最短。
证明：假设第一辆加油的汽车的加油时间不是最短，即 。
则 对应的汽车必然在后面加油的某一辆汽车中，不妨设其为第 辆汽车，其他汽车的
加油顺序不改变，则新的总等待时间 满足：
T’-T=
由于 ， ，故上式成立，此时 ，因而不再满足最短等待时间的要求，
故不符合要求，假设不成立，即引理 1 成立
优化子结构：
引理 2：对于需要等待加油的汽车集合 ，若加油顺序 是其一个优化解且第一个加油的
车辆为 ，则 是 的一个解。
证明：设 为 的解，由于 ，与 最小
矛盾，故引理 2 成立
(3).伪代码及算法复杂度:
算法：求解最短平均等待时间
输入：等待时间序列 ，车辆序列
输出：最短平均等待时间 和等待车辆序列
评论0