贪心算法在会场安排与硬币找零问题中的应用

"宋行健同学的算法实验作业，包括会场安排问题和贪心算法实现最少硬币找零问题的源代码及程序运行截图。" 本次作业主要涉及两个算法问题，分别是会场安排问题和最少硬币找零问题，这两个问题都可以通过贪心算法来解决。 首先，会场安排问题是一个典型的贪心策略应用。问题描述为：有n个活动，每个活动有开始和结束时间，需要找出最小的会场数量来容纳所有的活动。关键在于，贪心算法会选择局部最优解，即每次选择当前最佳的解决方案，希望最终能得到全局最优解。在本问题中，算法步骤如下： 1. 输入活动的开始和结束时间，存储在startTime[]和endTime[]数组中。 2. 对开始和结束时间数组分别进行升序排序。 3. 初始化会场数量room为0，以及一个变量j用于记录当前最早的结束时间。 4. 遍历排序后的开始时间数组，如果当前活动的开始时间小于已知的最早结束时间，说明需要一个新的会场，因此room++。否则，更新最早的结束时间为下一个活动的结束时间，j++。 5. 最终输出所需的会场数量room。 其次，最少硬币找零问题同样运用贪心算法。给定需要支付的金额Pay和不同面值的硬币，目标是最少使用多少硬币完成找零。这个问题的贪心策略是：每次都用最大面值的硬币找零，直到无法继续为止。代码中，CoinValue[]存储硬币面值，ChangeValue[]存储可能的找零面值，包括不找零的情况。算法步骤如下： 1. 初始化最少硬币数CoinNum为0。 2. 从大到小遍历硬币面值，用Pay除以当前面值，得到可以使用的硬币数量，更新Pay为剩余需要找零的金额。 3. 在每次找零后，将硬币数量累加到CoinNum，并更新Pay。 4. 循环结束后，CoinNum即为最少的硬币数。 这两个问题都展示了贪心算法在解决实际问题中的有效性，即通过每次选择局部最优解来逼近全局最优解。然而，需要注意的是，贪心算法并不总是能找到全局最优解，但在这两个问题中，它恰好能够给出正确答案。