常用几种算法

贪心，分治，回溯，动态规划四种算法。

贪心算法

场景：我们有m个糖果和n个孩子，现在要把糖果分给这些孩子吃，但是糖果少，孩子多即m<n，所以糖果只能分给一部分孩子。每个糖果的大小不等，m个糖果的大小分别是s1,s2,s3,...,sm。每个孩子对糖果大小的需求也不一样，只有糖果的大小大于等于孩子对糖果大小的需求时，孩子才得到满足。假设n个孩子对糖果大小的需求分别是g1,g2,g3,...,gn。

问题：如何分配糖果，能尽可能满足最多数量的孩子？

思路：对于一个孩子来说，如果小的糖果可以满足，就没有必要用更大的糖果，这样更大的糖果就留给其他对糖果大小需求更大的孩子。另一方面，对糖果大小需求小的孩子更容易被满足。所以，我们可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对我们期望值的贡献是一样的。所以每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

思想：每次都能够找到最优解，并且每次的最优解，能够构成最终解。

---

分治算法

场景：给10GB的订单文件按照金额排序，因为数据量大，有10GB，而我们机器的内存可能只有2，3GB这样子，无法一次性加载到内存，也就无法通过单纯地使用快排，归并等基础算法来解决了。

思路：要解决这种数据量大到内存装不下的问题，我们就可以利用分治思想。将海量数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。

解决：先给10GB的订单排序，我们就可以先扫描一遍订单，根据订单的金额，将10GB的文件划分为几个金额区间。比如订单金额在[1,100]的放到一个小文件，[101,200]放到另一个文件，以此类推。这样每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的10GB订单数据了。

思想：分治算法的核心思想其实就是四个字，分而治之，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并结果，就得到原问题的解。分治算法是一种处理问题的思想，递归是一种编程技巧。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

分解：将原问题分解成一系列自问题；解决：递归地求解各个子问题，若子问题足够小，则直接求解；合并：将子问题的结果合并成原问题。

---

回溯算法

场景：（8皇后问题）我们有一个8*8的棋盘，希望往里放8个棋子，每个棋子所在的行，列，对角线都不能有另一个棋子。八皇后问题就是期望找到所有满足这种要求的放棋子方式。

思路：把这个问题划分成8个阶段，依次将8个棋子放到第一行，第二行，第三行...第八行。在放置的过程中，不停地检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种方法，继续尝试。

代码如下：

思想：回溯算法思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是从一组可能的解中，选择出一个满足要求的解。可以用来解决八皇后，0-1背包问题，图的着色，旅行商问题，数独问题，正则表达式匹配等等。