计算机算法设计与分析_第三章_2.pdfVIP

第三章 贪心方法 1 第三章 贪心方法 3.1 一般方法 3.2 背包问题 3.3 带有限期的作业排序 3.4 最优归并模式 3.5 最小生成树 3.6 单源点最短路径 2 3.3 带有限期的作业排序  1. 问题描述 – 假定在一台机器上处理n个作业，每个作业均可在单 位时间内完成；同时每个作业i都有一个截至期限d 0, i 当且仅当作业i在其截至期限以前被完成时，则获得 p 0 的效益。 i – 问题： 求这n个作业的一个子集J ，其中的所有作业都可在其 截至期限内完成。——J是问题的一个可行解。 p – 可行解J 中的所有作业的效益之和是 ，具有最大  i iJ 效益值的可行解是该问题的最优解。 3.3 带有限期的作业排序  1. 问题描述 – 目标函数： p i iJ – 约束条件： 所有的作业都应在其期限之前完成 – 分析 如果所有的作业期限 “足够宽松”，而使得多有 作业都能在其期限之内完成，则显然可以获得当 前最大效益值； 否则，将有作业无法完成——决策应该执行哪些 作业，以获得最大可能的效益值。 4 3.3 带有限期的作业排序  1. 问题描述 – [例3.2] n=4，(p , p , p , p )=(100, 10, 15, 20)和(d , d , 1 2 3 4 1 2 d , d )=(2, 1, 2, 1) 。可行解如下表所示： 3 4 可行解 处理顺序 效益值 ① (1) 1 100 ② (2) 2 10 t1 t2 ③ (3) 3 15 d , d ④ (4) 4 20 2 4 ⑤ (1,2) 2,1 110 d , d 1 3 ⑥ (1,3) 1,3或3,1