贪心算法

Q：什么是贪心算法？

A：不管最后怎么样，先获得当前的最优解。所以贪心算法最后得到的解并不一定是最优解

       例子：一个袋子可以装4斤水果，现在有3斤苹果，2斤草莓，2斤葡萄，贪心算法就会直接先把苹果装进去，其实最优的是装2斤草莓2斤葡萄！

相关应用：

Prim算法、Kruskal算法、喷泉问题、会场问题、过河问题、01背包问题

什么是Prim算法？

从任意一个顶点开始，寻找与当前点最近的点，将两顶点的边加入到树中，构造出权值最小的生成树。

详细来说：

1.将图的所有点放到集合V内，从中选出任意一点作为点集U的起始点{v1}

2.寻找V—U中与U中的点可连接的权值最小的点，将点加入U中，从V—U中删去（注意此时不能形成环）

（实际算法中会引入一个辅助数组，记录从U到V—U的最小代价的边。所以这个辅助数组是实时更新的，例如：此时U{v1,v3}，那么在v3寻找关连边的点时，碰到了与v1也可以关联的点，并且v3与该点的权值小于v1，那么更新辅助数组）

3.重复2操作，直到V—U中的点为空，那么U中的点构成的树就是最小生成树

什么是Kruskal算法？

其实它也是构成最小生成树的算法，但是和Prim不同的是，Prim是根据点求出最小生成树，而Kruskal是根据边求出最小生成树。所以在边多的情况下，尽量不用Kruskal算法。

详细来说：

1.先将所有边按照权值由大到小进行排列

2.按照顺序选择边，如果该边的两个节点不属于同一个集合，那就将它合并，如果属于同一个集合，就舍弃此边，再寻找下一边，直到所有的节点都属于同一个集合。

那么这里发现一个问题，我们要如何将节点合并呢？

这里就出现了一个并查集方法。

什么是并查集？

1.查询元素a与b是否处于同一个集合内

2.合并元素ab为一组

并查集结构用树来实现，如下图，当我们要看两个元素是否相等，那么只需要看它们的根节点是否相等，如果相等就属于同一集合。而合并时只需要将两个根节点相连就可以。

简单的并查集算法会发现有一个巨大的缺点：极有可能退化成线性结构

那么这时候就需要用“路径压缩”和“按秩合并”阻止它的退化

什么叫路径压缩？

将原本与根节点间接相连的点变为与根节点直接相连，如下图

什么叫按秩合并（unit）？

对于每一棵树，记录它的高度。每次合并树时，将矮的树挂在高的树下

喷泉问题（一）：

作法：圆的内切正方形的边长为草坪的宽

喷泉问题（二）：

作法：1.舍去半径小于草坪宽二分之一的圆，

           2.记录其他圆形成的矩形边界，排序符合的矩形

           3.判断第一个矩形的左边界是否大于零，大于零则不存在符合喷泉装置将草坪润湿

           4.遍历矩形右边界，直到右边界大于矩形长度，结束遍历，输出count值

会场安排问题：

作法：1.vector存下所有活动，将活动按结束时间的近远进行排序

           2.变量a保存vector的大小。

           3.看第一个活动结束时间是否大于其他活动的开始时间，如果大于某一活动，a减1，否则查看该活动的结束时间是否大于其他活动的开始时间（如果上一个活动在t时间内结束，那么下一个活动应该在t+1时间开始）

过河问题：

作法：1.当N==1或N==2，直接过河

           2.当N==3，最快与次快先过河，最快的拿着手电筒返回，再与最慢的一起过河

           3.当N>=4，a[0]为最快的人过河时间，a[1]为次快，a[n-1]为最慢的人过河，a[n-2]为次慢。通过N=3,4,归纳总结可知，过河时间存在两个方案

            方案一：a[0]与a[n-1]先过河，a[0]返回再与a[n-2]过河

            方案二：a[0]与a[1]先过河，a[0]返回，a[n-1]与a[n-2]过河，a[1]返回，a[0]与a[1]过河

            过河时间的方案的差异只与a[0],a[1],a[n-2]有关,当a[0]+a[n-2]-2a[1]>0时选择方案一，小于0选择方案二，每执行一次就减少两人，直到人小于4为止

01背包问题：

作法：将物品价值最大的先放入背包

---

动态规划（大事化小）

Q：动态规划的特征是什么？

A：最优子结构、无后效性

      最优子结构：当前的最优状态可以由某个或某些状态直接得到

      无后效性：不管之前这个状态是如何得到的（比如迷宫问题，我们在记录当前路线的时候会影响到下一步路线的选择，这就是有后效性。os:搜索解决迷宫问题，搜索：每个阶段的最优状态都是由之前所有状态组合得到的。）

动态规划的实质：

1.分析问题，构造状态转移方程（通过最优子结构推导得出），注意边界问题

2.以空间换时间（什么是空间复杂性？支持计算所要用到的存储状态最多有多少

                            什么是时间复杂性？从初始状态到最终状态走了多少步）

动态规划的解题步骤：

1.确定子问题。（确定哪些变量随着问题规模的变小而变小）

2.确定状态。（给子问题限定状态）

3.推导出状态转移方程（根据子问题进行推导）

4.确定边界

5.确定实现方式

6.确定优化方法（有时候会发现当执行到步骤5时就会返回步骤1继续执行，中间就会有很多重复部分，所以这时候就要采用：降维问题、优先队列、四边形不等式优化等）

相关题目：

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。

    1.假设只差最后一步就可以踏上第10级台阶，那么此时有两种方法，一个是站在第九级台阶往上走一步，另一个是站在第八级台阶往上走两步。

    2.假设走到九级有X种方法，走到八级有Y种方法，那么走到十级就是X+Y，所以这里可以得出递推方程：F(n)=F(n-1)+F(n-2)

    其实当我们推导出一个递推的方程F(n)=F(n-1)+F(n-2)，如果直接用递推方式去解决，那么会存在很多重复的计算（当我们求F(n),要得到F(n-1),F(n-2)的值，要得到F(n-1)，就要得到F(n-2),F(n-3)的值，可以看出F(n-2)计算了两次）。

    如果我们将F(n-1),F(n-2)存储起来，那么求解F(n)就只需要一步加法，此时时间复杂性降低，空间复杂性增加，这就叫做空间换时间。（这就叫做“备忘录算法”，备忘录算法保留所有子状态，它与动态规划的最大的不同就是它是“自顶向下”，动态规划是“自底向上”）

    再思考一下，能不能把空间复杂性缩小，那么我们自底向上，用迭代方式求出结果，台阶的走法数量由前两个台阶数量相加而成。所以我们根本不需要把所有的子状态都记录，只需要记录当前状态的前两个状态，就可以求出当前状态。这就是动态规划的实现

最长公共子序列问题（LCS）：

解题思路：

设A=“a0,a1.....am-1”,B="b0,b1...bn-1",Z="z0,z1...zk-1",Z为AB的最长公共子数列

1.当am-1==bn-1时，则查找"a0,a1...am-2"与"b0,b1...bn-2"的最长公共子序列

2.当am-1!=bn-1时，则在"a0,a1,....am-2"与"b0,b1..bn-1" 和 "a0,a1,....am-1"与"b0,b1..bn-2"中找到最长的公共子序列

最长递增子序列问题（LIS）：

解题思路：

1.因为是查找子序列而不是子串，所以递增序列不需要连续。

2.外层遍历给定数组，内层遍历外层 i之前的数

    那么我们需要判断 a[ j ] < a[ i ] （以及Dp( i ) < Dp( j ) + 1），就可以给子序列的长度加1，所以得出状态转移方程为 Dp( i ) = Dp( j ) + 1

优化上面的算法：

    将数一个一个插入队列中，如果发现当前数大于队尾数，那么就插在队尾，反之就用二分法查找大于当前数的最小值的位置，替换为当前数。

01背包问题：

解题思路：

设B(i)为背包价值，W(i)为物品重量，V[i]为物品价值，capacity为背包可以放的最大容量

1.物品有放和不放两种状态，那么如何判断放进去的东西能使利益最大化呢？

2.当背包当前容量比物品重量还小时，不能再放进东西，这时背包的价值与前面B(i-1)价值相等

3.当背包容量可以再放进物品，但装了也不一定达到当前的最优价值，所以在装与不装之间选择最优的一个，

装进物品：

    就是取{w1,w2,w3....wi-1}的物品，装入体积为当前背包剩余容量减去要装进的物品wi容量，所得到的最大值再加上要wi的价值。

不装入：

    就是取{w1,w2,w3....wi-1,wi}的物品，装入当前背包容量，所得的最大价值

从上面两种找出最优价值即可，所以装不装只第i-1个物品有关。

完全背包问题：

解题思路：

1.这个时候和01背包就不一样了，01背包是有取或者不取的策略，而这里则是取0种、取1种...等策略

2.解题思路与01背包略微相似

   但是就是在背包容量可以放下东西时不同，这时候我们也需要在装与不装之间选择