贪心算法
先来比较一下贪心算法和动态规划
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择，不考虑整体，只考虑局部最优，所以它不一定能得到最优解；
动态规划则是每个步骤都要进行一次选择，但选择通常要依赖子问题的解，所以它是考虑整体的，由于通常要依赖子问题的解，所以一般选自自底向上自带备忘的机制，所以一定是最优解；
最优子结构的概念
如果一个问题的解包含其子问题的最优解，则称该问题具有最优子结构，也就是求解大问题的解，是通过求解小问题取解决
如果理解了最优子结构，则会发现贪心算法和动态规划都利用了最优子结构的性质
实现该算法的过程
从问题的某一初始解出发
while 能朝给定总目标前进一步 do
求出可行解的一个解元素
由所有解元素组合成问题的一个可行解
典型的可用贪心来解的问题有
最小生成树、分数背包问题（类似0-1背包问题，只不过可以取物体的一部分）
用分数背包问题举个例子
W=30（所选物体不能超过30）
物品：A B C
重量：20 5 20
价值：40 20 20
这个时候的贪心选择肯定是选择单位价值量最高的
所以先选择B，再选择A
再从C中选择5
这时价值肯定最大
但贪心算法一开始就说了，并不保证最优解，所以有时会配合随机算法（算法导论第三版第五章有讲）使用
一般来说贪心算法的代码比动态规划简单的多
回溯算法
回溯法概念
通常采取深度遍历的形式，按照某种规则的能够避免某些不必要搜索的穷举式搜索
解空间（所有解的集合）
可以组织成一棵解集合的树
解集合树中的节点分为几种
扩展节点
在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个结点就成为一个新的活结点，并成为当前扩展结点。
死节点
如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点，此时应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点，用这种方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止
典型问题
货担郎问题（TSP问题）
设某售货员要到若干城市去推销商品，已知各城市之间的路程（或路费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程最小。
这是解集合树（具体怎么解决这个问题，再分子界限算法中解决，这里只是介绍回溯法本身）
利用回溯法解决该类问题步骤
1、针对所给问题，定义问题的解空间；
2、确定易于搜索的解空间结构；
3、以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用剪枝函数（这里明白概念就行，具体在分支界限算法讲）
用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。
具体例子，0-1背包问题和TSP问题，将在下一章结合分支界限介绍，这章只介绍概念
