算法分析习题参考答案第四章.doc

第四章作业 部分参考答案 设有个顾客同时等待一项服务顾客需要的服务时间为应该如何安排个顾客的服务次序才能使总的等待时间达到最小总的等待时间是各顾客等待服务的时间的总和试给出你的做法的理由证明 策略 对进行排序然后按照递增顺序依次服务即可 解析设得到服务的顾客的顺序为则总等待时间为则在总等待时间T中的权重最大的权重最小故让所需时间少的顾客先得到服务可以减少总等待时间 证明设下证明当按照不减顺序依次服