贪心算法解析：找硬币与活动安排问题

"本章作业涉及的是第4讲的贪心算法内容，主要讨论了贪心算法的基本思想、要素和实例分析。作业中提到了教材P142上的习题4-3，4-11，4-16，4-18，4-24。" 贪心算法是一种解决问题的策略，它在每一步决策时都采取当前状态下最佳的选择，以期望最终达到全局最优解。这种算法并不考虑整个问题的全局最优解，而是着眼于当前情况，做出局部最优决策，希望这些局部最优的累积能够导致全局最优。 在第4章中，通过找硬币的例子阐述了贪心算法的应用。例如，找给顾客6角3分时，贪心算法会选择每次都找最大面值的硬币，直到金额满足为止，这种策略在某些情况下确实能得到最少硬币数的解。然而，当问题变为找1角5分时，贪心算法（先选1角1分再选4个1分）就不再是最佳解，因为选取3个5分硬币是更优的选择，这展示了贪心算法并不总是能得到全局最优解。 接着，介绍了活动安排问题作为贪心算法的一个应用实例。在这种问题中，多个活动需要共享同一资源，如会议室，每个活动都有起始和结束时间，目标是选择最多的不冲突活动。贪心算法可以按照结束时间最早的顺序选择活动，这样每次选择的活动都不会与之前已选的活动冲突，从而尽可能多地安排活动。 在活动安排问题的定义中，有n个活动，每个活动都有起始时间si和结束时间fi，如果两个活动的结束时间早于另一个活动的起始时间，那么这两个活动是相容的，可以同时进行。贪心算法的策略是，每次选取结束时间最早的未被选中的活动，以确保选择的活动集合是最大的相容集合。 总结来说，贪心算法是一种基于局部最优解的策略，适用于某些问题，如单源最短路径问题和最小生成树问题，但在某些情况下，如找硬币或活动安排问题，它可能无法保证全局最优解。尽管如此，贪心算法在很多实际问题中仍然是一个高效的解决方案，因为它简单且计算量小，尤其在没有明确的全局最优解时，它可以提供一个接近最优的解。在学习和应用贪心算法时，理解它的局限性和适用范围至关重要。