"马丙鹏_计算机算法设计与分析_第四章_贪心方法"

马丙鹏在《计算机算法设计与分析》一书的第四章中介绍了贪心方法。该章节包括一般方法、背包问题、带有限期的作业排序、最优归并模式、最小生成树和单源点最短路径等内容。 其中，4.3节主要讨论了带有限期的作业排序问题。该问题假设有n个作业需要在一台机器上完成，每个作业都可以在单位时间内完成。每个作业都有一个截至期限，如果一个作业在其截至期限以前被完成，则会获得一定的效益。问题的目标是找出一个子集J，其中包含所有能在其截至期限内完成的作业。可行解J中的所有作业的效益之和即为问题的最优解。 为了解决这个问题，需要分析作业的截至期限和效益，并根据其截至期限的宽松程度进行决策。如果所有作业的期限都足够宽松，使得所有作业都能在期限内完成，那么就可以得到当前的最大效益值。但如果有作业的期限过紧，无法在期限内完成，就需要选择执行哪些作业才能获得最大的效益值。 对于带有限期的作业排序问题，贪心算法可以有效地求解。具体算法包括以下步骤： 1. 将所有作业按照截至期限从小到大排序。 2. 选择第一个作业执行，并将其效益累加到总效益上。 3. 对于后续的作业，依次判断其截至期限是否足够宽松以便在期限内完成。 4. 如果某个作业的截至期限紧迫，无法在期限内完成，则忽略该作业。 5. 如果某个作业的截至期限足够宽松，则选择执行该作业，并将其效益累加到总效益上。 6. 继续判断下一个作业，重复步骤4和步骤5，直到遍历完所有作业。 7. 返回总效益作为最优解。 通过贪心算法解决带有限期的作业排序问题，可以得到一个在有限期内完成作业的最优解。该算法的时间复杂度为O(nlogn)，其中n为作业的数量。 贪心算法的优点在于其简单、高效，并且在一些实际问题中可以取得较好的结果。然而，贪心算法并不适用于所有问题，因为贪心选择的局部最优解不一定能够得到全局最优解。因此，在使用贪心算法时需要根据具体问题的特点进行分析和验证。针对不同的问题，可能需要采用其他更为复杂的算法来求解。总之，贪心方法是一种重要的算法设计思想，在算法设计与分析中具有广泛的应用。