贪心算法解排队打水问题-ACM入门实践

"贪心算法是ACM竞赛中常见的解决问题的方法，尤其在面对优化问题时，如排队打水问题和部分背包问题。贪心算法的基本思想是在每一步选择中都采取在当前状态下最好或最优的选择，希望通过每一步的局部最优解，能够逐步得到问题的全局最优解。 在排队打水问题中，有n个人需要在r个水龙头打水，每个人装满水桶所需的时间不同。为了使所有人花费的总时间最小，我们应当让装水时间最短的人优先打水，因为这样可以尽早释放水龙头，让更多人有机会打水。假设第i个人打水需要ti分钟，那么最优的顺序应该是按照时间从小到大排序。这样，当第i个人完成打水时，其他人等待的总时间是最少的。例如，输入为4个人和2个水龙头，装水时间为6, 4, 5，按照贪心策略排序后，最优顺序是4, 5, 6, 6，总时间为4+5+6+6=21分钟。 贪心算法在ACM竞赛中常用于解决具有明显局部最优选择性质的问题，如上述的部分背包问题。部分背包问题中，有一个最大容量为m的背包，n种食品，每种食品有wi公斤，价值为vi元/公斤。为了最大化总价值，我们应优先选择单位重量价值最大的食品，直到背包无法再装入任何物品。这种策略确保了每次选取的都是当前条件下最好的选择，从而期望得到整体价值的最大化。 贪心算法的关键在于证明局部最优解可以导出全局最优解。在贪心策略适用的问题中，通常具备以下特征： 1. 局部最优解能导向全局最优解：每一步的贪心选择都应该有助于最终的最优解，就像在部分背包问题中，选择单位重量价值最大的食品。 2. 最优子结构：问题的最优解可以通过其子问题的最优解构建，即子问题的最优解组合起来可以构成原问题的最优解。在背包问题中，不论怎么选择，第一次选择的价值最大的单位食品，都是最优解的一部分。 然而，贪心算法并不总是有效，对于某些问题，比如旅行商问题或完全背包问题，单纯的贪心策略并不能保证得到全局最优解。在应用贪心算法时，必须对问题进行深入分析，确保贪心选择性质成立，否则可能会导致错误的解决方案。 总结来说，贪心算法是一种有效的求解优化问题的策略，尤其在问题具有明显的局部最优选择和最优子结构特点时。在ACM竞赛中，掌握贪心算法可以帮助参赛者快速找到问题的解决方案，提高解题效率。"