目录第十二章.数据结构及算法应用第一节.分治法第二节.回溯法第三节.贪心法第四节.动态规划法第五节.哈夫曼编码第十二章.数据结构及算法应用第一节.分治法其基本思想是把一个比较大的、复杂的问题，拆分成一些比较小的子问题，如快速排序算法基本原则1.该问题的规模缩小到一定的程度就可以容易地解决2.该问题可以分解为若干个规模较小的相同问题3.利用该问题分解出的子问题的解可以合并为该问题的解4.该问题所分解出的各个子问题是相互独立的分治法——递归技术递归，就是在运行的过程中调用自己基本原则图注：该算法的目的是求这样一个数列，由零开始的，每一个数都等于前面两个数之和的数列，该算法操作即：将 F(3)转换为 F(1)和 F(2)之和，F(4)转换为 F(2)和 F(3)之和 这样可以使所有的 F(n)都能化为 F(1)和 F(0)的和分治法——二分法查找第二节.回溯法基本原则概念：回溯法是一种选优搜索法，按选优条件向前搜索，以达成目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新进行选择。这种走不通就退回一步再继续往下走的技术就是回溯法第三节.贪心法基本原则1.概念：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每一步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解经典实例——背包问题图注：有三个物品(每种物品仅存一个)，其容量分别为：20，30，40；其价格分别为：140，180，200；而背包可容纳的总量为 70，我们希望背包中能容纳尽可能多的物品，其容纳的物品价值最高，而贪心法则会根据单位容量价值最高的原则优先将这个物品进行容纳，如物品 1 的每 10 个容量其价值为 70，物品 2 则为 60，物品 3 则为 50；因此，若采用贪心法，其将会优先放入物品 1到背包中，然后放入物品 2，此时空间只剩下 20，无法装下物品 3，因此，方案到此结束，采用该方法得到了总价 320 的物品，但这显然不是最优解，我们将物品 3 和物品 1 装入背包，得到的物品总价值为 340第四节.动态规划法1.概念：在求解问题时，对于每一步决策，列出各种可能的局部解，再根据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解，在动态规划法中，基本上都要用到查表这一步骤第五节.哈夫曼编码1.概...
