1贪心算法的设计思想是什么，囿什么特点如果一个问题用贪心算法可以获得全局最优解，那么该问题的求解应满足哪些条件

答：贪心算法的设计思想是在对问题求解时，总是做出在当前看来是最好的选择

它的特点是1）不是从整体考虑——得到的解可能不是全局最优 2）简单，直接易理解，效率高

如使用贪心算法求解问题获得全局最优解，则问题应满足

1）贪心选择性质（与动态规划的主要区别）

所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到

2）最优子结构性质（动态规划算法和贪心算法的共同点）

一个问题的最优解包含其子问题的最優解时

用贪心法求解的问题应具备两个特性：

2，贪心法与动态规划法的比较

答：贪心法：当前状态下局部最优选择，然后求解作出此選择之后的子问题贪心选择依赖于以往作出的选择，但不受将来所作的选择既不依赖于子问题的解。

动态规划法：每步所作的选择依賴于相关子问题的解只有在解出相关子问题以后，才能作出选择

3，如何证明一个问题具有贪心选择性质

答：思路：证明每步贪心选擇à问题的整体最优解。

1）假设问题有一个整体最优解

2）修改这个最优解，使其以贪心选择开始并且证明修改后的解仍然为最优解。

3）运用数学归纳法证明：

    因为作出贪心选择以后，根据最优子结构性质原问题转化为规模更小的子问题。

,小于任意货箱.所以得到解

n  例：字符出现频率与编码方案

若需要下载请务必先预览（下載的文件和预览的文件一致）

由于本站上传量巨大，来不及对每个文件进行仔细审核尤其是在

质量、数量、时间上的核对，一旦你付费丅载本站将不予退款。