贪心法学习笔记

1、田忌赛马问题

2、贪心算法：

依贪婪准则作出决策，逐步构造解值。又叫登山法，根本思想是逐步到达山顶，即局部最优逐步达到全局最优。

3、贪心算法的特点：

4、贪心算法的三个性质

a.原问题的最优解包含其子问题的最优解

b.问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

a.通过一系列局部最优的选择（贪心选择）达到全局最优

b.这是贪心算法与动态规划算法的主要区别

问题的全过程可以分为若干个阶段，而且在任何一个阶段x后的行为都只仅仅依赖于x的状态，而与x之前如何达到这种状态的方式无关。这样的过程就构成了一个多阶段决策过程。

5、贪心法处理问题的核心是贪婪准则的选取，难点是最优解的证明。

6、背包问题课后习题

7、基本要素课后习题

8、MST课后习题

9、哈夫曼编码课后习题