《算法导论》笔记

本文最后更新于：2022年8月2日 19:38

概论

重要特性 输入、输出、确定性、有限性

算法描述 自然语言、流程图、伪代码、程序代码

算法的复杂性 时间复杂性、空间复杂性

算法的渐进性态

$O(g(n))$ 上界

$Ω(g(n))$ 下界

$Θ(g(n))$ 确界

$logn < n < nlogn < n^2 < n^3 <2^n$

NP完全理论 能在多项式时间内求解的判定性问题称为P问题，在多项式时间能验证猜测解的正确性为NP问题

递归与分治

递归概念

递归定义 用函数自身定义的函数 GNU is Not Unix

递归函数两个要素 边界条件与递归方程

满足条件 可转化（可以转化为一个或者多个子问题，子问题的求解方法与原问题完全相同，只在规模上不同）、调用次数有限、有结束递归的条件来终止递归，并不是所有递归都可以转换

何时使用递归 定义是递归的（斐波那契），数据结构是递归的（链表），问题的求解方法是递归的（汉诺塔，数的排列）

递归算法转化为非递归算法

直接转化法：直接用循环结构的算法替代递归算法，不需要使用栈
用栈模拟系统的运行过程，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法，需要使用栈

排列问题

Template<class type>
void Perm(Type list[], int k, int m)
{
//递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有
	if (k==m) { //只剩下一个元素
		for (int i=0;i<=m;i++) cout<<list[i];
        cout<<endl;
    }
    else//还有多个元素，递归产生后缀是list[k:m] 的全排列
	for(i=k;i<=m;i++) {
		Swap(list[k],list[i]);
    	Perm(list,k+1,m);
    	Swap(list[k],list[i]); //记得还原
    }
}

整数划分

对于数据n，最大加数不大于m的划分个数记作q(n,m)

$q(n,m) = \left\{\begin{matrix} 1 & n = 1,m = 1\\ q(n,n) &n<m \\ 1+q(n,n-1) &n = m \\ q(n,m-1)+q(n-m,m) &n>m>1 \end{matrix}\right.$

分治概念

设计思想 将一个难以直接解决的大问题，分割成一些规模较小的子问题，这些子问题互相独立且与原问题相同，从而递归地解子问题，将各个子问题的解合并得到原问题的解

适用问题 该问题可以分解为若干个规模较小的相同问题；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；该问题的规模缩小到一定的程度就可以容易地解决；利用该问题分解出的子问题的解可以合并为该问题的解

求解过程 分解、求解、合并

时间复杂性计算 扩展递归技术、递归树、主定理方法

▲主定理方法 T(n)=aT(n/b)+f(n)，其中a≥1，b>1为常数，该方程描述了算法的执行时间，算法将规模为n的问题分解成a个子问题，每个子问题的大小为n/b。比较两个式子大小即可

$T(n) = aT(\frac{n}{b} ) + f(n) =\left\{\begin{matrix} O(n^{log_{b}a } ) & n^{log_{b}a} > f(n)\\ O(n^{log_{b} a }log_2 n) & n^{log_{b}a} = f(n) \\ O(f(n)) & n^{log_{b}a} < f(n) \end{matrix}\right.$

二分搜索

问题描述 给定已按升序排好序的n个元素a[1:n]，现要在这n个元素中找出一特定元素x

代码

int BinarySearch(Type a[ ], const Type &x,int n)
{
	int left=0;	int right=n-1;
	while(left<=right){
		int middle=(left+right)/2;
		if(x==a[middle])
			return middle;
		else if(x>a[middle])
			left=middle+1;
		else
			right=middle-1;
	}
	return -1; 
}

解释

指针left在什么情况下会超过right?

Left指针向左移动, right指针向右移动，如果一直没有找到结果，那么这两个指针最终会重叠，指向同一个位置。此时队列中只剩下一个元素。

此时，left=right；因此middle=left=right；

如果这个元素满足x==a[middle]，程序结束 return middle；

否则如果x>a[middle], left=middle+1后，left将位于right的右边；

否则如果x<a[middle], right=middle-1后，right将位于left的左边

大整数乘法

问题描述 XY是n位二进制整数，计算他们的乘积XY

$\begin{array} {X}X=A2^{\frac{n}{2}}+B, Y=C2^{\frac{n}{2}}+D \\ XY = AC2^n+(AD+BC)2^{\frac{n}{2} }+BD \\ =AC2^n+((A-B)(D-C)+AC+BD)2^{\frac{n}{2}}+BD \\ T(n) = O(n^{log3}) =\left\{\begin{matrix} O(1) & n=1\\ 3T(\frac{n}{2} ) + O(n) & n>1 \\ \end{matrix}\right. \end{array}$

Strassen乘法

问题描述 计算两个矩阵相乘的结果，分块矩阵计算

$\begin{array} {X} T(n) = O(n^{3}) =\left\{\begin{matrix} O(1) & n=1\\ 8T(\frac{n}{2} ) + O(n^2) & n>1 \\ \end{matrix}\right. \end{array}$

解释两个 n/2×n/2 的矩阵相加：一行需要n/2次加法，共有n/2行，因此，两个矩阵相加的复杂度为 n/2×n/2=n^2/4，四次矩阵相加的复杂度为 O(n^2)

改进算法 只需要七次乘法

棋盘覆盖

问题描述 2^k阶的棋盘中只有一个方格残缺，要求用L型骨牌覆盖残缺棋盘上的所有方格且任何2个L型骨牌不得重叠覆盖，用递推求解时间复杂度

$\begin{array} {X} T(k) = O(4^{k}) =\left\{\begin{matrix} O(1) & k=0\\ 4T(k-1 ) + O(1) & k>0 \\ \end{matrix}\right. \end{array}$

解释测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1) ，覆盖4个残缺子棋盘（ 2^(k-1)阶）需四次递归调用，共需时间4T(k-1)

合并排序

问题描述 数组排序

temlplate  <class type>
void MergeSort(Type a[], int left, int right)
  {   if (1eft < right) //至少有2个元素
       {  
       int i = (left + right ) /2; //取中点
       MergeSort(a, 1eft, i)；
       MergeSort(a, i+1, right)；
       Merge(a, b, 1eft, i, right)；//从a合并到数组b
       copy(a, b, left, right);//复制回数组a
     }
 }

$\begin{array} {X} T(n) = O(nlogn) =\left\{\begin{matrix} O(1) & n=1\\ 2T(\frac{n}{2} ) + O(n) & n>1 \\ \end{matrix}\right. \end{array}$

快速排序

问题描述 数组排序

template <class Type>
void QuickSoft(Type a[], int p, int r) {
    if(p<r) {
        int q=Partition(a, p, r)
        //找到q的位置
        //同时确保该位置右边的比基准元素大，左边的比基准元素小
        QuickSort(a, p, q-1); //对左半段排序
        QuickSoft(a, q+1, r); //对右半段排序
        }
     }

int Partition(Type a[],int p , int r ) {
    int i = p; j = r+1;
    type x = a[p];
	while(true) { 
         while(a[++i] < x && i < r);
         while(a[--j] > x);
         if (i >= j) break;
         swap(a[i],a[j]);
    }
    swap(a[p], a[j]);
    return j;
}

//随机选择基准点的快速排序
template <class Type>
void randomizedQuickSoft(Type a[], int p, int r) {
    if (p<r) {
        int q=randomizedPartition(a, p, r);
        randomizedQuickSort(a, p, q-1); //对左半段排序
        randomizedQuickSoft(a, q+1, r); //对右半段排序
        }
}

template <class Type>
int randomizedPartition(Type a[], int p, int r) {
    int i=random(p, r);
    swap(a[i], a[p]);
    return Partition (a,p,r);
}

解释

步骤
- 分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任意一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]，下标q在划分过程中确定
- 递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序
- 合并
最坏情况，已经排好，O(n^2)
最好情况，每次划分大小都是n/2，O(nlogn)

线性时间选择

问题描述

无序排列中求n个元素中第k小的元素（主要求中位数）。

template <class Type>
Type RandomizedSelect (a[], int p,int r, int k) {
    if (p==r) return a[p];
    int i = RandomizedPartition(a, p, r), //前面有
    j = i-p+l  //统计前半部分元素个数j,  i为基准点
    if ( k <= j )
        return RandomizedSelect(a, p, i, k);
    else
        return RandomizedSelect(a, i+1, r, k-j);
}

解释

根据随机产生的基准点，将元素分为2组，基准点包含在第1组中；如果k<=j，则第k小元素落在a段，为a段的第k小元素；如果k>j，则a段的所有元素都比第k小元素还要小，第k小元素落在b段，为b段中的第k-j小元素（-j的含义是去掉a段的元素总个数）

最坏情况，分成两个1和n-1的子问题，O(n^2)

最好情况，每次都产生n/2大小的子问题，O(n)

基准点选择优化

例如可以分成五个组，取每组中位数的中位数。设所有元素互不相同。在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x,因此，找出的基准x至少比3(n-5)/10个元素大。同理，基准x也至少比3(n-5)/10个元素小。当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

Type Select(Type a[], int p, int r, int k) {
    if (r-p<75) {
        TO DO//用某个简单排序算法对数组a[p:r]排序;
        return a[p+k-1];
    for ( int i = 0; i<=(r-p-4)/5; i++ ) {
        //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置;
        Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);
        int i=Partition(a,p,r, x),
        j=i-p+1;
        if (k<=j) return Select(a,p,i,k);
        else return Select(a,i+1,r,k-j);
    }
}

例题

a=[2,6,9,1,4,10,20,6,22,11,10,9,4,3,7,16,11,8,2,5,4,1]

寻找第5小元素

(要求两个中位数选择较小的一个，支点放在第一个列表中)

解答

$n=22$，分组如下

[2,6,9,1,4] [10,20,6,22,11] [10,9,4,3,7] [16,11,8,2,5] [4,1]

中位数集合[4, 11, 7, 8, 4]，选择中位数的中位数为7作为支点

把支点放在第一个列表中

划分a[0:11]=[2, 6, 1, 4, 6, 4, 3, 2, 5, 4, 1, 7]
a[12:21]=[9, 10, 20, 22, 11, 10, 9, 16, 11, 8]

对a[0:11]继续分组 [2,6,1,4,6],[4,3,2,5,4],[1]

中间元集合:[4,4,1]，中间元的中间元为4作为支点

把支点放在第一个列表中，划分：[2,1,4,4,3,2,4,1] [6,6,5]

对a[0:7]继续分组 [2,1,4,4,3],[2,4,1]

中间元集合:[3,2]，中间元的中间元为2作为支点

划分：[2,1,2,1] [4,4,3,4]

第一组小于5了

取第二组第5-4=1小的，也就是3

最接近点对

一维情况

1) 将S上的n个点分成大致相等的2个子集S1和S2
2) 分别求S1和S2中的最接近点对
3) 求一点在S1、另一点在S2中的最接近点对
4) 从上述三对点中找距离最近的一对

二维情况

m为S中各点x间坐标的中位数，构造S1和S2 O(n)
递归求S1和S2的最小距离 2T(n/2)
求上述两个距离的最小值dm
设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在d之内所有点组成的集合；将P1和P2中的点依其y坐标值排序；并设X和Y是相应的已排好序的点列 O(nlogn)
通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离； O(n)
选择dm dl的最小值

循环赛日程表

问题描述 设有n(n = 2^k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手要与其他n-1位选手比赛一场，且每位选手每天必须比赛一场，不能轮空。

发现规律

动态规划

概念

基本思想 基本思想是在对一个多阶段决策的问题，按照某一顺序，根据每一步所选决策的不同，会引起状态的转移，最后会在变化的状态中获取到一个决策序列。

基本要素

最优子结构性质（分析问题是否满足最优性原理（用反证法）：①先假设由问题的最优解导出的子问题的解不是最优的；②再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾）
子问题重叠性质（子问题不相互独立，重复出现，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解）

算法步骤

分析最优解的性质，并刻画其结构特征；
递归地定义最优值；
以自底向上或自顶向下的方式计算出最优值；
根据递归计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解。

矩阵连乘

问题描述 每计算出一个元素，需要q次乘法，最终得到的矩阵是p×r矩阵，有p×r个元素，因此，计算C需要的乘法次数为q×p×r。每次要选择较小的q×p×r。给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，且i=1,2⋯,n-1,如何确定计算矩阵连乘积的计算次序，使得计算矩阵连乘的数乘次数最少。

$m[i][j]=\left\{\begin{array}{cc} 0 & i=j \\ \min_{i\leq{k}<j} \{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\} & i<j \end{array}\right.$

解释矩阵连乘积从Ai到Aj定义为A[i:j]，A[i:j]最少的乘法次数定义为m[i,j]，最优断开位置k记为𝑠[i,j]=k，T(n)=O(n^3)

例题

计算矩阵连乘积A[1:6]的最少数乘次数，其中各矩阵的维数分别为p=[30,35,15,5,10,20,25]

解答
$\begin{matrix} 𝑚[1][2]=𝑚[1][1]+𝑚[2][2]+p_0p_1p_2=15750 \\𝑚[2][3]=𝑚[2][2]+𝑚[3][3]+p_1p_2p_3=2650 \\... \\m[1][3]= \min \left\{\begin{matrix} m[1][1]+m[2][3]+p_0p_1p_3=7875▲ \\m[1][2]+m[3][3]+p_0p_2p_3=18000 \end{matrix}\right. \\s[1][3]=1 \\... \\m[2][6]= \min \left\{\begin{matrix} m[2][2]+m[3][6]+p_1p_2p_6=0+5375+35*15*25=18500 \\m[2][3]+m[4][6]+p_1p_3p_6=2625+3500+35*5*25=10500▲ \\m[2][4]+m[5][6]+p_1p_4p_6=4375+5000+35*10*25=18125 \\m[2][5]+m[6][6]+p_1p_5p_6=7125+0+35*20*25=24625 \end{matrix}\right. \\s[2][6]=3 \\... \end{matrix}$

m A1 A2 A3 A4 A5 A6

A1 0 15750 7875 9375 11875 15125

A2 0 2625 4375 7125 10500

A3 0 750 2500 5375

A4 0 1000 3500

A5 0 5000

A6 0

s A1 A2 A3 A4 A5 A6

A1 0 1 1 3 3 3

A2 0 2 3 3 3

A3 0 3 3 3

A4 0 4 5

A5 0 5

A6 0

从右上角的元素开始分割，从A3后面分为A[1,3]与A[4,6]，s[1,3]=1，从A1后面拆分，s[4,6]=5，从A5后面拆分，得到((A1(A2A3)((A4A5)A6)，次数最少是15125

m	A1	A2	A3	A4	A5	A6
A1	0	15750	7875	9375	11875	15125
A2		0	2625	4375	7125	10500
A3			0	750	2500	5375
A4				0	1000	3500
A5					0	5000
A6						0

s	A1	A2	A3	A4	A5	A6
A1	0	1	1	3	3	3
A2		0	2	3	3	3
A3			0	3	3	3
A4				0	4	5
A5					0	5
A6						0

最长公共子序列

void LCSLength
(int m,int n, char *x, char *y,int c[][], int b[][]) {
    int i, j;
    for (i=1;i<m;i++) c[i][0]=0;
    for (i=1;i<n;i++) c[0][i]=0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //m,n是X和Y的长度
            if (x[i]==y[j]) {
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=1;
            } else if (c[i-1][j]>=c[i][j-1]) {
                c[i][j]=c[i-1][j];
                b[i][j]=2;
            } else {
                c[i][j]=c[i][j-1];
                b[i][j]=3;
            }
        }
    }
 }

void LCS(i, j, X, b) {
    if (i==0 || j==0) return;
    if (b[i,j]=="1" ) {
        LCS(i-1, j-1, x, b);
        cout <<x[i];
    } else if (b[i,j]=="2" ) 
       LCS(i-1, j, x, b);
    else LCS(i, j-1, x, b);
}   //计算复杂性：O(m+n)
//LCS(i, j, X, b)实现根据b的内容打印出Xi与Yj的最长公共子序列。
//调用LCS(m,n,x,b) 可打印出序列X和Y的最长公共子序列。

$c[i][j]=\left\{\begin{array}{cc} 0 & i=0, j=0 \\ c[i-1][j-1]+1 & i, j>0 ; x_{i}=y_{j} \\ \max \{c[i-1][j], c[i][j-1]\} & i, j>0 ; x_{i} \neq y_{j} \end{array}\right.$

解释 c[i,j]记录序列Xi和Yj的最长公共子序列长度，b[i,j]可以记录是哪种类型。在c表中从最右下角的那个元素开始，看b表中对应位置的值，如果为1，则在c表中从当前位置往左上角走；如果为2，则在c表中从当前位置往正上方走；如果为3，则在c表中从当前位置沿水平方向往后退一位；依次类推，直到c表中箭头退到c[0，0]为止。

补充两个序列的最长公共子序列不唯一，不影响最长公共子序列的长度；但是可能会产生不一样的公共子序列，见例题

例题

给定两个序列为X=ABCBDAB和Y=BDCABA，求最长公共子序列。

解答
$\begin{matrix}i=1,X_1=\{A\} \\j=1,Y_1=\{B\},𝑐[1][1]=\max⁡\{ 𝑐[0][1],𝑐[1][0]\}=0, b[1][1]=2 or 3 \\j=2,Y_2=\{BD\},𝑐[1][2]=\max⁡\{ 𝑐[0][2],𝑐[1][1]\}=0, b[1][2]=2 \\... \\j=4,Y_4=\{BDCA\},𝑐[1][4]=c[0][3]+1=1, b[1][4]=1 \\... \\i=7,X_7=\{ABCBDAB\} \\j=6,Y_6=\{BDCABA\},\max⁡\{ 𝑐[6][6],𝑐[7][5]\}=4, b[7][6]=2 or 3 \end{matrix}$

斜线箭头尾部位置对应的元素为公共子序列元素（下标从1开始），也就是有BCBA（x[2346]与y[1356]）\BCAB（x[2367]与y[1345]）\BDAB（x[4567]与y[1245]）

PS: 对于C[1,1]=max{c[0,1],c[1,0]}={0,0}=0等情况，此时，b[1,1]=2或3都可以，不影响最终的结果。可能有多个答案。

最大子段和

问题描述 n个整数组成的序列，求该序列连续子段和的最大值（规定当所有
整数均为负整数时定义其最大子段和为0）

int MaxSum(int n, int *a) {
    int sum=0, b=0;
    for (int i=1; i <= n; i++) {
        if (b>0) b+=a[i];
        else b=a[i];
        if (b>sum) sum=b;
    }
    return sum;
}

$b[j]= \max\{b[j-1]+a[j],a[j]\}(1\leq j \leq n)$

解释 b[j]为以a[1,j]之间的任一位置开始，以a[j]为结束的最大子段和（必须要到j才行）。从i开始，到j-1结束的子段和的最大值<=0，从i开始到j结束的子段和的最大值应该为a[j]自身。从i开始，到j-1结束的子段和的最大值大于0，此时，将a[j]加上（不是因为如果a[j]小于零就不加了，b[j]的定义就是要加到j），所得到的值应该是从i开始，到j结束的子段和的最大值。 O(n)

例题

a[1:6]=[-2,11,-4,13,-5,-2]

解答
$\begin{matrix} j=1,𝑏[1]=\max\{𝑏[0]+𝑎[1],𝑎[1]\}=-2,i=1 \\j=2,𝑏[2]=\max\{𝑏[1]+𝑎[2],𝑎[2]\}=11,i=2 \\j=3,𝑏[3]=\max\{𝑏[2]+𝑎[3],𝑎[3]\}=11-4=7,i=2 \\j=4,𝑏[4]=\max\{𝑏[3]+𝑎[4],𝑎[5]\}=7+13=20,i=2 \\j=5,𝑏[5]=\max\{𝑏[4]+𝑎[5],𝑎[5]\}=20-5=15,i=2 \\j=6,𝑏[6]=\max\{𝑏[5]+𝑎[6],𝑎[6]\}=15-2=13,i=2 \end{matrix}$
比较各个$b[i]$，其中最大的就是最大子段和，也就是$b[4]=20$,$i=2$开始，$j=4$结束，也就是$[11,-4,13]$

凸多边形最优三角剖分

问题描述 给定一个凸多边形以及定义在由多边形的边和弦组成的三角形上的权函数$w$。求一个三角剖分，使得剖分中诸三角形上的权之和为最小。

$t[i][j]=\left\{\begin{array}{cc} 0 & i=j \\ \min_{i\leq{k}<j} \{t[i][k]+t[k+1][j]+w(v_{i-1}v_kv_j)\} & i<j \end{array}\right.$

解释

定义$t[i][j]$为凸子多边形的最优剖分对应权函数值， $s[i][j]$记录了$v_{i-1}$和$ v_j$一起构成三角形的第3个顶点$k$的位置，据此，用$O(n)$时间就可以构造出
最优三角剖分中的所有三角形。

计算最优值与矩阵连乘积相似。计算凸$n+1$多边形的最优值为$ t[1][n]$

例题

（好难算啊不会考吧）

图像压缩

问题描述 数字化图像是的像素阵列。假定每个像素有一个0~255的灰度值，存储一个像素需8位。为了减少存储空间，采用变长模式，即不同像素用不同位数来存储。

线性化：图片拉直，转换为$1×n^2$向量
分段：分成连续的$m$段，每段像素存储位数相同，每段最多含256个像素点
存放信息：第$i$段长度（8bit），第$i$段中像素存储位数（3bit）

$\begin{matrix} s[i]=\min\limits_{1 \leq k \leq \min \{i,256\}}\{s[i-k]+k*bmax(i-k+1,i) \}+11 \\bmax(i,j)=\max\limits_{i\leq k \leq j}\{a[k]\} \end{matrix}$

解释

假设$s[i]$是序列${p_1,p_2,…,p_i}$的最优解，$a[i]$是第i个像素点的位数。

假设$p_i$自成一段，则$s[i]=s[i-1]$+保存$p_i$的代价
取$s[i]$为min时对应的元素个数为$k$，$s[i]=s[i-k]$+保存最后$k$个像素的代价
保存最后$k$个像素的代价=$k*max${$k$个灰度值二进制位数}+11

例题

求像素序列4，6，5，7，129，138，1的最优分段。

解答
$\begin{matrix} a=[3,3,3,3,8,8,1] \\s[0]=0 \\s[1]=s[0]+1*\max \{3\} +11=14 \\s[2]= \min \left\{\begin{matrix} s[0]+2* \max \{3,3\} + 11 = 17▲ \\s[1] + 1*\max \{3\} +11 =28 \end{matrix}\right. \\... \\s[7]= \min \left\{\begin{matrix} s[0]+7* \max \{3,3,3,3,8,8,1\} + 11 = 67 \\s[1]+6* \max \{3,3,3,8,8,1\} + 11 = 73 \\... \\s[4]+3* \max \{8,8,1\} + 11 = 58▲ \\... \\s[6]+1* \max \{1\} + 11 = 62 \end{matrix}\right. \end{matrix}$
看s[7]=58，看58那一行是s[4]+3*max，前四个一起，后三个一起

看s[4]=23，看23那一行是s[0]+4*max，前四个就在一起，不再分

最后得到（4，6，5，7）（129，138，1）

ps每次计算比大小可以不加上11但是最后求$s$的时候别忘了加11

电路布线

问题描述 确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线且不相交

$\begin{matrix} i=1, \qquad Size(i,j) = \left\{\begin{matrix} 0 && j<\pi(1) \\1 && j \geq \pi (1) \end{matrix}\right. \\ \\i>1,\qquad Size(i,j) = \left\{\begin{matrix} Size(i-1,j) && j<\pi(i) \\\max \{ Size(i-1,j),Size(i-1,\pi(i)-1)+1\} && j \geq \pi (i) \end{matrix}\right. \end{matrix}$

解释 MNS(i,j)表示上面序号小于i，连接到下面的序号都小于j的不相交的集合，最后要求MNS(n,n)。如果j=pi(i)，如果（i,pi(i)）不在MNS中，将i点删除没有影响，就是size(i,j)=size(i-1,j)，如果（i,pi(i)）在MNS中，就是size(i,j)=size(i-1,pi(i)-1)+1

例题

已知[(1 8)(2 7)(3 4)(4 2)(5 5)(6 1)(7 9)(8 3)(9 10)(10 6)]，求最大不相交情况

解答

i=1，pi(1)=8，j>=8的size都为1

i=2，pi(2)=7，j<7的size为size(1,j)，j>=7的size为size(1,j)与size(1,6)+1=1的最大值

i=3，pi(3)=4，j<4的size为size(2,j)，j>=4的size为size(2,j)与size(2,3)+1=1的最大值

…

最后size(10,10)=4，最多可以有四条不相交。

蓝色是算法选择的路径（向上优先，也可以用向左优先，答案都是四个，但值会有一点不同）。在斜角值改变时可以取得所求的子集。答案也就是[(3 4)(5 5)(7 9)(9 10)]，[(4 2)(5 5)(7 9)(9 10)]

流水作业调度

问题描述 n个作业要在两台机器M1和M2上进行加工。每个作业加工的顺序都是先在M1上加工，然后在M2加工。M1和M2加工作业i所需的时间分别为ai 和bi。确定n个作业的最优加工顺序，使得加工完成所需的时间最少。

算法

N1集合存放ai<bi的作业，N2存放ai≥bi的作业
N1中作业按照ai升序排序，N2中作业按照bi降序排序
N1连接N2，计算时间

例题

任务 J1 J2 J3 J4 J5 J6

工序1 30 120 50 20 90 110

工序2 80 100 90 60 30 10

解答

分集合 {1,3,4}{2,5,6}

排序 {4,1,3}{2,5,6}

合并与计算时间

任务 J4 J1 J3 J2 J5 J6

M1结束 20 50× 100× 220× 310× 420↓

M2开始 20 60 140 230 330 420

M2结束 80↗ 160↗ 250↗ 350↗ 380× 430

ps：第k个任务M2开始的时间要取第k个任务M1结束的时间和第k-1个任务M2结束的时间的较大值。

任务	J1	J2	J3	J4	J5	J6
工序1	30	120	50	20	90	110
工序2	80	100	90	60	30	10

任务	J4	J1	J3	J2	J5	J6
M1结束	20	50×	100×	220×	310×	420↓
M2开始	20	60	140	230	330	420
M2结束	80↗	160↗	250↗	350↗	380×	430

0-1背包

问题描述 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。问如何选择装入背包中的物品使得装入物品的总价值最大？

$\begin{matrix} m(i,j) = \left\{\begin{matrix} m(i+1,j) && 0 \leq j<w_i \\ \max \{ m(i+1,j),m(i+1,j-w_i)+v_i\} && j \geq w_i \end{matrix}\right. \\ \\m(n,j) = \left\{\begin{matrix} 0 && 0 \leq j<w_n \\ v_n && j \geq w_n \end{matrix}\right. \end{matrix}$

解释 m[i,j]表示可选择物品i, i+1, …, n时，背包容量为j装入的最大价值

例题

n=5,c=10,W={2,2,6,5,4},V={6,3,5,4,6}

解答

i=5时，j<4时，装不进去，为0，j>=4时，能把w5=4装进去，为v5=6

i=4时，若j<5，则w4=5无法放入，m(4,j)=m(5,j)，j>=5时，比较m(5,j)与m(5,j-5)+4的最大值（可以看作先直接把m(5,j)往上复制一行，j>=5时再比较更新即可，后面同理）

i=3时，若j<6，则w4=6无法放入，m(3,j)=m(4,j)，j>=6时，比较m(4,j)与m(4,j-6)+5的最大值

… 最后结果如下图

当

从m(1,10)开始看起，m(1,10)!=m(2,10),说明1肯定被放入了背包中。1的重量为2，剩下的容量为10-2=8；

从m(2,8)开始看起，m(2,8)!=m(3,8),说明2肯定被放入了背包中。2的重量为2，剩下的容量为8-2=6；

从m(3,6)开始看起，m(3,6)=m(4,6),说明3肯定没有放入背包中。继续m(4,6)=m(5,6),说明4肯定没有放入背包中。

当i=5时，看剩余的容量，如果满足5号物品的重量，则5肯定放入。否则，5无法放入。此例，容量为6，5号物品重量为4，5号物品放入。

最后得到放入的五件物品状态为(1,1,0,0,1)

贪心

概念

思想在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策。它并不一定对所有问题都成功，因为不从整体最优加以考虑，贪心解法可能不是全局最优解，但是对某些问题特别简单、有效。

基本要素

最优子结构性质 问题的最优解包含其子问题的最优解
贪心选择性质 问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到，当前的选择和子问题的解无关，只和以往做出的选择有关

活动安排

问题描述 在活动集合中选择最大的相容活动子集合

template<class Type>
void GreedySelector(int n,Type s[],Type f[],bool A[] {
    //s存开始时间，f存结束时间，且按结束时间非减续排列；
    A[1]=true; //排在第1个的活动最先结束，直接放入A；
    int j=1;
    for (int i=2;i<=n;i++) {
       //从第2个活动开始检测
       if (s[i]>=f[j]) { A[i]=true; j=i; }
       //如果相容，放入A
       else A[i]=false;
    }
}

证明贪心选择性质

假设问题有一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。
运用数学归纳法证明，每一步贪心选择→问题的整体最优解

例题

1 2 3 4 5 6 7 8 9 10 11

start 5 0 3 5 3 1 8 6 8 12 2

stop 9 6 5 7 8 4 11 10 12 14 13

解答

待安排的11个活动按结束时间的非减序排列

6 3 2 4 5 1 8 7 9 11 10

start 1 3 0 5 3 5 6 8 8 2 12

stop 4 5 6 7 8 9 10 11 12 13 14

最后为(6,4,7,10)

	1	2	3	4	5	6	7	8	9	10	11
start	5	0	3	5	3	1	8	6	8	12	2
stop	9	6	5	7	8	4	11	10	12	14	13

	6	3	2	4	5	1	8	7	9	11	10
start	1	3	0	5	3	5	6	8	8	2	12
stop	4	5	6	7	8	9	10	11	12	13	14

0-1背包

几种贪心策略（但是都不能保证得到最优解）

选择可以装入背包的价值最大的物品
选择可装入背包的重量最小的物品
选择可装入背包的vi/wi最大的物品（一般用来做回溯法或者分支限界的限界函数）

最优装载

策略重量最轻的先装 T(n)=O(nlogn)

template <class Type>
void Loading(int x[], Type w[], Type c, int n ) {
    int *t = new int [n+1];
    Sort(w, t, n) ; //按货箱重量排序/
    for (int i = 1; i < = n; i ++)
    x[i] = 0;
    for (int i = 1;i<= n && w[t[i]] <= c; i++) {
        [t[i]] = 1;
        c-= w[t[i]];
    }
}

例题

(100,200,50,90,150,50,20,80), c=400

解答

所考察货箱的次序为73684152，考察到5时装不下了

(100,200,50,90,150,50,20,80) 装了390

(1,0,1,1,0,1,1,1)

哈夫曼编码

前缀码 对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀，这种编码称为前缀码。

问题描述 找到使平均码长达到最小的前缀码编码方案

策略频率小的字符，深度大。队列Q以f(c)为键值存放二叉树各结点，通过贪心选择，将最小频率的两个二叉树合并，然后将新树（频率为上述两个二叉树频率之和）插入Q中。 T(n)=O(nlogn)

证明贪心选择性质

设x和y是字符集C中具有最小频率的两个字符，证明存在C的最优前缀码，使x和y具有最长、相同的码长且仅最后一位编码不同。设二叉树T表示C的任意一个最优前缀码方案。只要证明可以对T做适当修改后，得到一棵新的二叉树T’，新树中，x和y是最深叶子且为兄弟。同时，新树也是C的最优前缀码方案。

证明最优子结构性质

设T表示C的一个最优前缀码方案。x和y是树T中的叶子节点且为兄弟。z是它们的父亲。若将z看做是具有频率f(z)=f(x)+f(y)的字符，则证明树T’=T-{x,y}表示字符集C’=C-{x,y} U {z}的一个最优前缀码即可。

例题

设在1000个字母的文章中各字母出现的频率为a:83, b:14, c:28, d:38, e:131, f:29, g:20, h:53……，求最优编码。

解答

ps:注意兄弟节点左小右大（按题目规定）

单源最短路径(dijksta)

dijksta视频演示

例题

解答

回溯

概述

特点深度优先搜索策略、算法框架是解空间（子集树与排列树）、在搜索的时候要避免遗漏，同时要高效。（具有限界函数的深度优先生成法称为回溯法）

解空间 子集树（0-1，装载，子集和）与排列树（旅行商，m着色，n后）

基本元素 活结点（自身已生成但其儿子还没有全部生成），拓展结点（正在产生儿子的结点），死结点（不满足约束或者所有儿子已经产生的结点）

剪枝用约束函数在扩展结点处剪去不满足约束的子树（左剪枝），用限界函数剪去得不到最优解的子树（右剪枝）

终止条件 找到所有的解，解空间中没有活结点为止

装载问题

问题描述 n个集装箱要装到2艘载重量分别为c1,c2的货轮，其中集装箱 i的重量为wi。要求找到装载方案将这n个货箱装上这2艘轮船

解释若装载问题有解, 采用如下策略可得一个最优装载方案：将第一艘轮船尽可能装满，将剩余的货箱装到第二艘轮船上。将第一艘船尽可能装满类似0-1背包问题

例题

n=4,c1=12,W={8,6,2,3}

解答

0-1背包

解释子集树。只要左儿子节点是一个可行结点，搜索就进入左子树（不超过背包重量）（约束剪枝）。在右子树中有可能包含最优解是才进入右子树搜索，否则将右子树剪去（利用单价贪心求解价值上限）（限界剪枝）。$cw$是背包当前重量，$M-cw$是背包剩余的空间，$cp$是当前总收益，$rp$是贪心算法剩余的物品收益，$bestw$记录当前最优价值，也就是判断$bp=cp+rp>bestw$是右节点的限界函数。（此外，回溯法解0-1背包的前置条件是物品已按$p_i/w_i$非增次序排序）

例题

M=110

w=(1,11,21,23,33,43,45,55)，v=(11,21,31,33,43,53,55,65)

解答

0 1 2 3 4 5 6 7

w 1 11 21 23 33 43 45 55

v 11 21 31 33 43 53 55 65

v/w 11 1.9 1.48 1.43 1.3 1.23 1.22 1.18

最优解为(1,1,1,0,1,1,0,0)

	0	1	2	3	4	5	6	7
w	1	11	21	23	33	43	45	55
v	11	21	31	33	43	53	55	65
v/w	11	1.9	1.48	1.43	1.3	1.23	1.22	1.18

n后问题

问题描述 皇后问题要求在一个n×n的棋盘上放置n个皇后，使得它们彼此不受”攻击”。n皇后问题要求寻找在棋盘上放置这n个皇后的方案，使得它们中任何两个都不在同一行、同一列或同一斜线上。

int nQueen(int n) {
    Queen X；
    //初始化X    
    X.n=n；//皇后个数
    X.sum=0；
    int*p=new int [n+1]；
    for(int i=0；i<=n；i++) p[i]= 0；
    X.x=p；
    X.Backtrack(1)；
    delete [] p；
    returnX. sum;
}

bool Queen:: Place(int k) {
    for (int j = 1; j < k; j++)
      if ((abs(k-j) == abs(x[j] - x[k])) 
        ||(x[j] == x[k] ))
          return false;
    return true;
}
 
void Queen:: Backtrack(int t) {
    if (t > n) 
        sum++;
    else {
      for (int i = 1;i <= n;i++) {
         x[t] = i;
         if (Place(t)) 
             Backtrack(t+1);
      }
    }
}