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

"计算机算法设计与分析【王晓东电子工业出版社2版】第4章.pptx" 本章主要探讨了贪心算法这一重要的算法设计策略。贪心算法是一种基于局部最优选择来解决问题的方法，它每次选取当前状态下最优的解决方案，期望通过连续的局部最优决策达到全局最优解。然而，贪心算法并不保证对所有问题都能找到整体最优解，例如在找硬币的例子中，对于不同的硬币面值和目标金额，贪心算法可能无法得出最小硬币数量的解。 贪心算法的关键特性包括两个基本要素： 1. 最优子结构：问题的最优解可以通过子问题的最优解来构造。即，解决大问题的最佳方式是通过解决一系列小问题的最佳方式来组合。 2. 贪心选择性质：在每一步选择中，都采取当前状态下最优的选择，希望以此达到全局最优。 贪心算法与动态规划算法的主要区别在于，动态规划会考虑所有可能的决策序列，并存储中间结果以避免重复计算，而贪心算法则在每一步都做最优选择，不考虑未来的后果。 本章还提到了几个贪心算法的应用范例： - 活动安排问题：在有限资源下，如何安排一系列相互冲突的活动，使尽可能多的活动得以进行。贪心算法通常会选择结束时间最早的活动优先，这样可以最大化兼容的活动数量。 - 最优装载问题：涉及到如何在有限容量的容器中装载物品，以达到最大的装载量。贪心策略可能是按物品重量降序装载，直至容器满载。 - 哈夫曼编码：一种数据压缩方法，通过构建最小带权路径长度的二叉树来生成最短的编码。 - 单源最短路径：寻找图中一个起点到所有其他顶点的最短路径，Dijkstra算法是一个典型的贪心解决方案。 - 最小生成树：在加权无向图中找到一棵包括所有顶点的树，使得树的所有边权重之和最小，Kruskal's算法和Prim's算法都是贪心方法。 - 多机调度问题：如何在多台机器上分配任务，以最小化总的完成时间。 虽然贪心算法不一定总能得到全局最优解，但在某些问题上，如单源最短路径和最小生成树问题，它确实能给出最优解。而且，即使在不能保证全局最优的情况下，贪心算法的解也往往是全局最优解的良好近似。 贪心算法是计算机科学中的一种重要策略，它在很多实际问题中都有广泛的应用。理解和掌握贪心算法的基本原理和应用技巧，对于优化问题的求解具有重大意义。