算法策略
1 穷举
1.1 穷举概述
- 穷举法又称列举法，其基本思想是逐一列举问题所涉及的所有情况。
- 穷举法常用于解决“是否存在”或“有多少种可能”等问题。
- 应用穷举法时应注意对问题所涉及的有限种情形须一一列举，既不能重复，又不能遗漏。
- 穷举通常应用循环结构来实现。在循环体中，应用选择结构实施判断筛选，求得所要求的解。
1.2 例子
百鸡百钱问题
已知：公鸡5元一只，母鸡3元一只，小鸡一元3只。现用100元钱买了100只鸡。
问：公鸡母鸡小鸡各几只？（请考虑尽可能高效的方法）
实际上上面的问题直接用数学的方法是不容易解出来的，因为未知数的个数多余方程的个数。这时就可以用到穷举法，列出所有的可能性。
分析：
假设0只公鸡，0只母鸡，0只小鸡。结果???
假设0只公鸡，0只母鸡，1只小鸡。结果???
假设0只公鸡，0只母鸡，2只小鸡。结果???
......
假设0只公鸡，1只母鸡，0只小鸡。结果???
假设0只公鸡，1只母鸡，1只小鸡。结果???
假设0只公鸡，1只母鸡，2只小鸡。结果???
......
......
假设1只公鸡，0只母鸡，1只小鸡。结果???
假设1只公鸡，0只母鸡，2只小鸡。结果???
假设1只公鸡，0只母鸡，3只小鸡。结果???
......
......
......
假设100只公鸡，100只母鸡，100只小鸡。结果???
以上共有101*101*101(即1030301)种可能情况。
这种思想，就是穷举思想，适合：问题的答案可能没有很直接的逻辑推理，但可以将所有“可能答案”都罗列出来，并且具有一定的规律性。
1.3 参考网址
- https://blog.csdn.net/Yeoman92/article/details/52683641
- https://my.oschina.net/Clarences/blog/1501708(穷举思想)
- https://zh.wikipedia.org/wiki/%E6%9A%B4%E5%8A%9B%E7%A0%B4%E8%A7%A3%E6%B3%95(维基百科)
2 贪婪
2.1 贪心概述
是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优值)的一种解题方法。 贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所作出的选择只是在某种意义上的局部最优解。
2.2 例子
找零钱问题
有三种硬币，1元、5角、1角。 现在要找一个2元7角的钱，怎样找才能使得硬币数最少。
步骤
(1) 首先找出一个面值不大于2元7角的最大硬币，即1元 (2) 然后，2元7角 - 1元，得到1元7角，找不大于1元7角的最大硬币，即1元 (3) 然后，减去1元，得到7角，找不大于7角的最大硬币，即5角 (4) 然后，减去5角，得到2角，找不大于2角的最大硬币，即1角 (5) 然后，减去1角，得到1角，找不大于1角的最大硬币，即1角 (6) 然后，减去1角，得到0角，找钱过程结束。
背包问题
问题描述 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
活动安排
问题描述： 设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。要求设计程序，使得安排的活动最多。
最小生成树
求一个连通无向图的最小生成树的代价（图边权值为正整数）。
小船过河
POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间最多的两个旅行者送到对岸去，有两种方式： 1.最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来，所需时间为：t[0]+2t[1]+t[n-1]； 2.最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来，所需时间为：2t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时最长的两人而不影响其它人，问题具有贪心子结构的性质。
区间覆盖
POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。
销售比赛
在学校OJ上做的一道比较好的题，这里码一下。假设有偶数天，要求每天必须买一件物品或者卖一件物品，只能选择一种操作并且不能不选，开始手上没有这种物品。现在给你每天的物品价格表，要求计算最大收益。首先要明白，第一天必须买，最后一天必须卖，并且最后手上没有物品。那么除了第一天和最后一天之外我们每次取两天，小的买大的卖，并且把卖的价格放进一个最小堆。如果买的价格比堆顶还大，就交换。这样我们保证了卖的价格总是大于买的价格，一定能取得最大收益。
哈夫曼编码
Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息，如果用01串表示字符，采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300000位；采用变长编码表示，给频率高的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码比定长码方案好，总码长减小约25%。
Dijkstra算法
Dijkstra算法是由E.W.Dijkstra于1959年提出，是目前公认的最好的求解最短路径的方法，使用的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点，简单的说就是bfs+贪心算法的思想。
2.3 参考网址
- https://blog.csdn.net/tanxuan231/article/details/47086127（找零钱）
- https://www.jianshu.com/p/50f1d4e0555c(背包，活动安排，最小生成树)
- https://blog.csdn.net/qq_32400847/article/details/51336300(背包，活动安排，多机调度问题，小船过河，区间覆盖， 销售比赛, 最小生成树，哈夫曼编码，)
- https://www.cnblogs.com/chinazhangjie/archive/2010/12/02/1894314.html(最小生成树)
- https://blog.csdn.net/will130/article/details/46335447(最小生成树)
3 分治
3.1 分治概述
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之‘
3.2 例子
合并排序
排序问题
快速排序
排序问题
大整数乘法
求两个大数A、B乘积的准确结果
其中A和B均为100位以上的十进制整数
A和B的位数可以不相等
最近对问题
在二维平面上的n个点中，找出最接近的一对点
3.3 参考网址
- https://blog.csdn.net/dd864140130/article/details/50859687(合并排序)
- https://blog.csdn.net/disappearedgod/article/details/23599343(合并排序, 快速排序)
- https://blog.csdn.net/u011446177/article/details/52894191(大整数排序)
- https://blog.csdn.net/qq_18738333/article/details/51769465(大整数排序)
- https://www.jianshu.com/p/8bc681afbaff(最近对问题)
4 回溯
4.1 回溯概述
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
4.2 例子
八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
