本章习题-贪婪法 算法设计与分析

本章习题 本章习题 8.1 给出一个找零问题的实例，使得贪婪法不能输出一个最优解。 8.2 单机调度：单处理机上有 n 个运行时间分别为 t1 ,..., tn 的作业，这些 作业可以按任意顺序执行，一次只能执行一个作业。要求：安排一个 调度计划，使得所有作业花费在系统中的时间最少。（一个作业花费 在系统中的时间是该作业的等待时间与运行时间之和） 1）为该问题设计一个贪婪算法。 2）这个贪婪算法总是能够产生最优解吗？ 8.3 求背包问题最优解：n=7，W=15， (w1, w2, w3, w4, w5, w6, w7) = (2, 3, 5, 7, 1, 4, 1)， (v1, v2, v3, v4, v5, v6, v7) = (10,5,15,7,6,18,3)。 8.4 说明理由：贪婪法解0-1背包问题，不一定能求得最优解。 8.5 概要描述：旅行商问题的贪婪算法。 8.6 多机调度：n 台相同的处理机P1,...Pn 处理 m个独立作业 J1 ,..., Jm 。 任何作业可以在任意处理机上运行，但未完工前不允许中断或分割为 更小的子作业。已知作业J1 ,..., Jm的运行时间为t1 ,..., tm 。设计一种 贪婪调度算法，使得m个作业在尽可能短的时间内完成。