贪心法一定能得到最优解

贪心算法（Greedy Algorithm）是一种求解最优化问题的有效方法，它在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。贪心法不同于动态规划，它不是通过回溯来寻求全局最优解，而是通过做出在当前看来是最好的选择来达到全局最优的目的。在具体应用的时候，一个问题能否使用贪心算法得到最优解，与问题本身和算法的设计密切相关。虽然贪心法并不是适用于所有问题的万能方法，但如果某一个问题具有贪心选择性质以及最优子结构的话，用贪心法就可以得到全局最优解，本文将从多个角度阐述贪心法一定能得到最优解。

一、问题具有贪心选择性质

贪心选择性质是指所做的选择必须是某种意义上的当前最优选择。具体来说，所谓的贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择（所谓的贪心选择）达到。贪心算法所作出的贪心选择是局部最优解，也就是在当前的状态下看起来是最好的选择，如果选择能够达到全局最优，那么问题就具有贪心选择性质。以最小生成树问题为例，使用Kruskal算法构造最小生成树的过程就是一个典型的贪心求解过程，每次选择当前能够连接到树上且权值最小的边，最终得到的就是整个图的最小生成树。

二、问题具有最优子结构

一个问题具有最优子结构性质是指其最优解可以通过一系列子问题的最优解推导得到。在使用贪心算法时，需要保证问题具有最优子结构性质，这样才能采用贪心选择来求解最优解。

三、减少计算量

在一些计算量极大的问题中，贪心算法可以大大减少计算量，从而既能够得到最优解，又能在较短的时间内处理出结果。比如在最优匹配问题中，每次取得最大利益点可以得到全局最优解。

四、可扩展性强

贪心算法天然的可扩展性强，可以通过问题的需求不断地进行扩展从而在保证全局最优的情况下找到一个更优解。比如在最少硬币找零问题中，每次尽量选择大面值硬币可以在保证总金额不变的前提下得到硬币个数最少的找零方案。

综上所述，一个问题能否使用贪心算法得到最优解取决于它是否具有贪心选择性质和最优子结构性质，如果满足这两个条件，那么使用贪心算法就可以得到全局最优解。此外，贪心算法还具有计算量少、可扩展性强等优点，适用于一些计算量大、复杂度高的问题。