Question

贪心算法的基本要素

Answer 1

贪心算法的基本要素：贪心选择性质和最优子结构性质。

1、贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心算法的局限性和分析过程

1、贪心算法的局限性：

贪心算法有他的局限性，有的时候我们选择局部的最优解，但是它对与全局并非最优解，就比如硬币找零问题。但是我们依然可以用我们上一章所学的动态规划思想来解决。

2、贪心算法的分析过程：

首先，我们需要确定我们的贪心策略，只有正确的贪心策略才能得出我们的结论。