中国科学院大学计算机学院计算机算法刘玉贵期末题库习题答案_第四章贪心算法.docx

1． 设有 n 个顾客同时等待一项服务。顾客 i 需要的服务时间为 ti ,1 ≤ i ≤ n 。 应该如何安排 n 个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。试给出你的做法的理由（证明）。 解：设调度f为: i1,i2,…,in，作业ik需等待，即作业1等待0，作业2等待i1，作业3等待i1+i2….，总的等待时间为：T(f)=。 使用贪心策略：服务时间短的作业先安排。算法描述略。 正确性：交换论证。不妨假设t1≤t2≤t2≤…≤tn,算法的调度f结果为1,2,..,n。设它不是最优的，存在最优调度f*，设其最早第k项作业ik与 f不同,即f*:1