算法设计经典算法总结

背包问题

0-1背包

题目：有一个容量为 V 的背包，和一些物品。这些物品分别有两个属性，体积 w 和价值 v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。

显然在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。

对于每一个物品，有两种结果：能装下或者不能装下。

• 第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的
• 第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。

然后确定状态即为背包容量为j时，求前i个物品所能达到最大价值，设为$dp[i][j]$dp[i][j]
初始时，将所有的$dp[0] [j]$dp[0][j](0<=j<=V)初始化为0，对应剩余大小为j的子背包，没有处理任何物品，因此也就没有价值。

然后确定状态转移方程
假设第i个物品的体积为w,价值为v，则状态转移方程为

• 如果j<w ,即为背包的剩余容量无法装载此物品，最大价值不变 $dp[i][j] = dp[i-1][j]$dp[i][j]=dp[i−1][j]
• 如果 j>=w， $dp[i][j]$dp[i][j] =$max (dp[i-1][j-list[i].w] + v, dp[i-1][j] ）$max(dp[i−1][j−list[i].w]+v,dp[i−1][j]） （在装载物品和不装载物品中取最大值）
  伪代码

list->物品数组
list[i].w->物品i的重量
list[i].v->物品i的价值
s-> 背包容量
n-> 物品总数

初始化二维数组
 for (int i = 0; i <= s; i++) dp[0][i] = 0;
 循环每个物品，执行状态转移方程
for (int i = 1; i <= n; i++)//
        {
        	对于背包容量可以装下物品的子问题
            for (int j = s; j >= list[i].w; j--)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - list[i].w] + list[i].v);
            }
            对于背包容量不可以装下物品的子问题
            for (int j = list[i].w - 1; j >= 0; j --)
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
结果
dp[n][s]->result

完全背包

扩展0-1背包问题，使每种物品的数量无限增加，便得到完全背包问题：有一个容积为 V 的背包，同时有 n 个物品，每个物品均有各自的体积 w 和价值 v，每个物品的数量均为无限个，求使用该背包最多能装的物品价值总和。

基于之前的结论
这时我们正序遍历j，正好可以实现每种物品的重复利用，即相当于每种物品有无限个。

 for (int i = 1; i <= n; i++)//循环每个物品，正序遍历j执行状态转移方程
        {
            for (int j = list[i].w; j <= s; j++) j从装载至少一个物品i开始
            {
            	注意此处，与0-1背包不同，这里为顺序，0-1背包为逆序
                dp[j] = max(dp[j]//不装载, dp[j - list[i].w] + list[i].v);//尝试尽可能多地装载
            }
        }
dp[s]-> result

最长公共子序列

给定一个序列X=<x1,x2,x3,x4…,xm>，另一个序列Z=<z1,z2,z3,z4…,zk>，若存在一个严格递增的X的下标序列<i1,i2,i3,…,ik>对所有的1,2,3,…,k，都满足x(ik)=zk，则称Z是X的子序列
如果Z既是X的子序列，又是Y的子序列，则称Z为X和Y的公共子序列

现在，设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

蛮力法求解最长公共子序列： 需要遍历出所有的可能，时间复杂度是O(n³)

使用动态规范法，经过分析，我们可以知道，可能会存在以下三种情况：

• 如果xm = yn，则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一个最长公共子序列

• 如果xm != yn 且 zk != xm，则Z是Xm-1和Y的一个最长公共子序列

• 如果xm != yn 且 zk != yn，则Z是X和Yn-1的一个最长公共子序列

如下图所示：

设

• p1表示X的前 i-1 个字符和Y的前 j 个字符的LCS的长度

• p2表示X的前 i 个字符和Y的前 j-1 个字符的LCS的长度

• p表示X的前 i-1 个字符和Y的前 j-1 个字符的LCS的长度

• p0表示X的前 i 个字符和Y的前 j 个字符的LCS的长度

如果X的第 i 个字符和Y的第 j 个字符相等，则p0 = p + 1

如果X的第 i 个字符和Y的第 j 个字符不相等，则p0 = max(p1,p2)

子问题的重叠性：

伪代码：
需要额外的数组空间 $B[m][n]和C[m][n]$B[m][n]和C[m][n]

搜索一遍，还需要构造优化解

• 从B[m, n]开始按指针搜索
• 若B[i, j]=“↖”，则$x_i=y_j$xi​=yj​是LCS的一个元 素
• 如此找到的“LCS”是X与Y的LCS

总时间复杂性为：O(mn)

比如说求ABCBDAB和BDCABA的LCS:

部分内容摘自博客：https://blog.csdn.net/weixin_40673608/article/details/84262695

任务安排问题（贪心法）

输入： Ｓ＝｛１,２，……，ｎ｝个任务，Ｆ＝｛［Ｓi ,f i］｝，为任务的开始时间和结束时间

输出： S的最大相容集合（也就是如何选择任务，才能执行最多的任务？）

贪心思想：
为了选择最多的相容活动，每次选fi最小的活动，也就是结束时间最小的活动，使我们能够余下更多的时间选择更多的活动。
这个在之前的blog写过，算法想起来也不难
https://blog.csdn.net/Franklins_Fan/article/details/107462914

最小生成树算法

回顾一下最小生成树：
对于图中的n个点，建立连通图（一定有n-1条边），使路径和最短的树结构

常见的有Kruskal(克鲁斯卡尔) 算法, Prim 算法，这个在数据结构课里面学过一点
prim算法适合稠密图 （边多）,kruskal算法适合简单图（点多）

Kruskal

使用并查集技术，贪心思想
将所有的边排序，然后依次选择最短的边，检查边的两个端点是否在一个并查集中
如果在的话，就跳过这两个端点，如果不在，边将这条边加入最小生成树中，并将其合并到一个并查集中

MST-Kruskal(G,W) 
 A=∅;  
 For  ∀v∈[G]   Do        
 	Make-Set(v);   /*  4. 按照W值的递增顺序排序E[G]; */
 For ∀(u,v)∈ E[G] (按W值的递增顺序)   Do
     If   Find-Set(u)！=Find-Set(v) Then  
     	A=A∪{(u, v)};  
     	Union(u, v);
Return  A 

贪心选择性：
设uv是G中权值最小的边，则必有一棵最 小生成树包含边uv.
设T是G的一棵最小生成树 ，若uv ∈T, 结论成立；
否则在T中添加uv边，就会产生环 ，删除环中不同于uv的权值最小的边xy,得到T’。 显然w(T’)=w(T)-w(xy)+w(uv) ≤w(T)

优化子结构：

Prim

设图的顶点集合为U，树的顶点集合为V
从图中任意一点出发，找到N-1条边(x,y)，x∈U，y∈V，且权值最小。
通俗的讲，就是不断找权值最小且不产生闭环的N-1条边

Prim算法是以点为对象，挑选与点相连的最短边来构成最小生成树。
而Kruskal算法是以边为对象，不断地加入新的不构成环路的最短边来构成最小生成树。

单源最短路径算法

dijkstra

不能有负权边

1. 从起点开始，查找所有与起点直接相连的点，并把连接它们的边权值作为起点到它们的距离(有平行边取最小值)。起点到起点的距离为0，其它不与起点直接相连的点距离为无穷大，存入一个表中。

2. 遍历所有点，查找得到的结果中距离最小的那个点，然后再看所有与该点直接相连的点，计算该点到它们的最短距离(即从起点开始，经由该点到达的点的距离)，根据结果更新上图。

3. 不断重复2中过程，直到每一个点都像2中那样计算过一遍。

Floyd

不能解决带有“负权回路”(或者叫“负权环”)的图

1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2. 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。