算法设计与分析

第1章算法概述

算法具有下述四个性质：输入、输出、确定性和有限性

而程序是算法使用某中程序设计语言的具体实现

算法的复杂度有时间复杂度和空间复杂度之分。

上面的三个式子分别是时间复杂度最好、最坏和平均复杂度。

渐进符号：$O、\Omega、\theta$。分别表示渐进上界，渐进下界，同阶。

NP完全性理论

将可由多项式时间算法求解的问题看作易解的问题，需要超多项式时间的问题看作难解问题。于是人们提出了非确定性的图灵机计算模型，使得许多问题可以在多项式时间内求解。

对于每一个最优解问题，都有一个与之对应的判定问题。所有可以在多项式时间内求解的判定问题构成P类问题（多项式问题）。

非确定性算法的概念：非确定性算法将问题求解分为猜测和验证两个阶段，算法的猜测阶段是非确定性的，给出问题解的一个猜测。算法的验证阶段是确定性的，验证猜测阶段给出解的正确性。P类问题是确定性计算模型下的易解问题类，NP类问题是非确定性的计算模型下的易验证问题类。所以所有非确定性多项式时间可解的判定问题构成NP类问题。

另一种叙述：

第2章递归与分治策略

一波总结

问题	时间复杂度	备注
二分搜索	$O(logn)$
大整数的乘法	$O(n^2)$或$O(n^{log_23})$…..
Strassen矩阵乘法	$O(n^3)$$O(n^{log_27})$$O(n^{2.376})$
合并排序	$O(nlogn)$
快速排序	最坏$O(n^2)$最好$O(nlogn)$
线性时间选择	$O(n)$
最接近点对问题	$O(nlogn)$

递归的概念

主要提到了许多问题：阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分、汉诺塔问题。其中整数划分问题的递归式和汉诺塔的伪代码如下：

分治法的基本思想

可能涉及到时间复杂度的计算

问题T可以划分为m个子问题，需要递归k次。其时间复杂度有两种计算方法：

主定理法：$aT(n/b)$和$f(n)$的问题规模，问题规模大的，说明其阶数大，即为主问题的主要时间消耗成分。$aT(n/b)$的时间复杂度可以用下式表示$O(n^{log_ba})$，所以比较$f(n)$和$aT(n/b)$的阶，只需要两者做比（类似洛必达的处理方式）：$\frac{n^{log_ba}}{n^{log_ba-\epsilon}}$。所以就有了如下内容：

迭代法：不想多说，就是求和，而且在某种情况下极度难求

二分搜索

已经排好序的n个元素搜索某个数字：

input x, a[n]
int left=0, right=n-1
while (left<right)
	int middle = (left+right)/2
    if (x == a[middle])
        return middle
    if (x > a[middle])
        left = middle + 1
    else
        right = middle - 1
return -1

时间复杂度为$O(logn)$

大数乘法

不是特别的固定，所以考的可能性不大吧。

正常的计算复杂度为$O(n^2)$。使用分治法的大数乘法：

所以对应的递归式：

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 4T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

如果非要考的话可能会考上式如何得到：AC表示A与C相乘，即两个$n/2$长度的整数相乘，同理，还要计算AD、BC、BD所以总共是$4T(n/2)$，$O(n)$表示位移和加法运算和。但是上述的时间复杂度还是$O(n^2)$

因为大数惩罚的的核心是减少乘法次数，所以可以化简成下式：

不难看出其对应的递归式：

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 3T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

此时时间复杂度为$T(n)=O(n^{log_23})$。（这里其实也体现了主定理方法求时间复杂度）至于觉得会考的部分可能是给出一个化简式让你写递归式，但是概率太小了……

Strassen矩阵乘法

大数相乘尚且需要$O(n^2)$，a*b与b*c的矩阵相乘需要$O(abc)$，方阵需要$O(a^3)$所以不太行。与大数乘法类似，核心是减少乘法次数，所以有两个方案：

正常人想出来的：

递归式为：

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 8T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

时间复杂度为$O(n^3)$

Strassen矩阵乘法：

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 7T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

时间复杂度为$O(n^{log_27})$

棋盘覆盖

都说了不考了，所以就不说了

合并排序

思想就是把数组分成两份，连接时排序，上伪代码：

input a[n], left, right
b[n] 为创建出来的空数组，用于保存结果
void MergeSort(a[], int left, int right)
    if (left < right)
        int mid = (left + right)/2
        MergeSort(a, left, mid)
        MergeSort(a, mid+1, right)
        Merge(a, b, left, mid, right)
        Copy(a, b, left, right)

时间复杂度：$T(n)=O(nlogn)$

$$\begin{equation} T(n)= \begin{cases} O(1)& \text{n=0}\ 2T(n/2)+O(n^2)& \text{n>1} \end{cases} \end{equation}$$

哦，真是优雅的屎代码啊，为了了解其实现的细节，我们来看看下面的代码（为了方便，代码并不符合c++规范）：

void MergeSort(int a[], int n)
    int b[n]={0,,,0}
	int s = 1 # 记录块大小，也可以表示递归层数
    while (s < n)
        MergePass(a, b, s, n)
        s += s
        MergePass(b, a, s, n)
        s += s

void MergePass(x[], y[], s, n)
    int i = 0
    while (i <= n-2*s)
        Merge(x, y, i, i+s-1, i+2*s-1)
        i = i+2*s
    if (i+s < n)
        Merge(x, y, i, i+s-1, n-1)
    else
        for(int j=i; j<=n-1; j++)
            y[j] = x[j]

void Merge(c[], d[], l, m, r)
    int i=l, j=m+1, k=l
    while ((i<=m) && (j<=r))
        if (c[i]<=c[j])
            d[k++] = c[i++]
        else
            d[k++] = c[j++]
        if (i>m)
            for(int q=j;q<=r;q++)
                d[k++]=c[q]
        else
            for(int q=i;q<=m;q++)
                d[k++] = c[q]

敲一遍的话不是很难理解，但是切记不要眼高手低，毕竟这代码自己写不出来。

快速排序

快排是基于分治的另一个排序方法，步骤为分解，递归求解，合并

void QuickSort(int a[], int p, int r)
    if (p < r)
        int q = Partition(a, p, r)
        QuickSort(a, p, q-1)
        QuickSort(a, q+1, r)

在我看来，快排是由基准和合并两个部分组成的，其基准方案是参考了什么排序算法来着？已经忘了

基准获取函数：

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

这就是那个一趟排序可以保证一个数字位置正确的算法。这一趟时间复杂度只有$O(r-p-1)$

但是上述总体的快排与划分是否对称有关，最坏的情况下为$O(n^2)$：

$$\begin{equation} T(n)= \begin{cases} O(1)& n\leq 1\ T(n-1)+O(n)& \text{n>1} \end{cases} \end{equation}$$

最好情况下是$O(nlogn)$

$$\begin{equation} T(n)= \begin{cases} O(1)& n\leq 1\ 2T(n/2)+O(n)& \text{n>1} \end{cases} \end{equation}$$

平均复杂度是$O(nlogn)$

可见该算法的时间复杂度取决于划分，可以考虑使用随机的划分方案。

线性时间选择

还是基于快排的思想，首先找到一个基准元素，一趟快排决定他的位置，判断是在左还是右，继续。

这个不是特别难，代码直接贴过来了：

Type RandomizedSelect(Type a[],int p,int r,int k) 
{
    if (p == r) 
		return a[p]; 
	int i = RandomizedPartition(a, p, r), j = i-p+l; 
	if (k<=j) 
		return RandomizedSelect(a, p, i, k); 
    else 
    	return RandomizedSelect(a, i+l, r, k-j);
}

其实和快排一样，速度在$\Omega(n^2)$到$O(n)$之间，但是平均性能很好。

那么能不能让算法在最坏的情况下还能$O(n)$？很离谱，根据主定理，我们只要让划分的时间复杂算法思路如下：

n个元素分为$n/5$组，每组5个元素，然后排序，取中位数，也就是获得了$n/5$个中位数
递归调用上面的算法

虽然不太懂，但是很nb，最后得到递归式

代码如下：

template<class Type> 
Type Select(Type a[], int p, int r, int k) { 
    if (r-p < 75) { 
        return a[p+k-1]; 
					}
	for (int i=0; i <= (r-p-4)/5; 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+l; 
		if (k <= j) 
			return Select(a,p,i,k); 
		else 
    		return Select(a,i+l,r,k-j)；
	}
}

第3章动态规划

同样，先准备一个小结：

感觉难的地方到了

问题	时间复杂度	备注
矩阵连乘	$O(n^3)$	最优值在dp[0][n]处
最长公共子序列	$O(mn)$ and $O(m+n)$	最优值在dp[m][n]处
最大子段和	$O(mn^2)$或$O(m(n-m))$	最优值在dp[n]处
凸多边形最优三角剖分	$O(n^3)$	最优值在dp[0][n]处
流水作业调度	$O(nlogn)$	最优值在dp[m][n]处
0-1背包问题	$O(min{nc,2^n})$	最优值在dp[i][j]处
最优二叉搜索树

首先分析一下动态规划的核心吧，类似分治，就是把问题分为子问题求解。但是存在的最大不同就是子问题之间是有关系的，所以不必要在分治的情况下花费指数倍的时间。

动态规划对应的有几个固定的步骤：

找出最优解的性质并刻画其结构特征
递归地定义最优解
自底向上的方式计算最优值
根据计算最优值得到的信息构造最优解

动态规划的有效性是基于它的两个形式：

最优子结构，通俗点讲，就是对最优解和原问题求相同的子集后，对应的解仍然为子集问题的最优解
重叠子问题，即在使用分治法计算时得到子问题并不总是新问题，也正是因此，我们会用到备忘录方法

矩阵连乘问题

直接上备忘录方法吧：

我们令p0~p7=[30,35,15,5,10,20,25]

对于该题，我们创建一个方阵

实际上每个坐标表示一个子问题，如m[2][5]就表示从第2个矩阵到第5矩阵连乘的最优解。

那么不难得知，m[i][i]=0所以先进行对角线的初始化。在此之后，开始计算第1与第2矩阵相乘的最优解，乃至第5到第6矩阵相乘的最优解，也就是上图的第二条对角线。以m[2][3]为例，该点的最优解计算就是p1*p2*p3。

这个还不是很难。那么对于m[2][4]，这个时候情况不一样了，其计算应该为：

$$\begin{equation} m[2][4]= min\begin{cases} m[2][2]+m[3][4]+p_1p_2p_4\ m[2][3]+m[4][4]+p_1p_3p_4\end{cases} \end{equation}$$

即第2个矩阵到第4个矩阵连乘的可能解有两种可能，即$(A_2)(A_3A_4)$和$(A_2A_3)(A_4)$而之前又求过m[3][4]和m[2][3]的最优解，所以…

基于上述内容，我们可以得到其递归式

$$\begin{equation} m[i][j]= \begin{cases} 0&i=j\ min{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j}&i<j\end{cases} \end{equation}$$

应该是难度比较合理的题目了，基于上述的递归式，我们也应该能大致得知其伪代码（但是这种考循环体的说实话不大可能，直接贴过来）

时间复杂度为$O(n^3)$因为要解矩阵，而且该矩阵每个值得通过多个计算比较最小值。

最长公共子序列

注意是序列而不是船，串必须连续但是序列不需要。

根据题目要求，给出两个序列X和Y，分别长度为m和n，还是基操，创建一个m*n的矩阵。那么每个坐标m[i][j]的意义为：n中前i个元素构成的序列与m中前j个元素构成的序列的最长公共子序列。

这道题并不难搞。感性的分析一下，无非就是两个序列从0开始，某一个长度加1，如果发现增加的元素是相同的元素，那么矩阵该位置的值相较于之前的状态+1，否则不变，把整个矩阵填完即可。

但是考虑到考试会考动态规划的证明，所以需要证明该问题有最优子结构性质。所以有如下的内容：

那么基于上面的分析，我们得到的子问题递归结构为：

因为每个单元的计算时间$O(1)$，所以整体的时间复杂度为$O(mn)$，回溯获得最长子序列的时间复杂度为$O(m+n)$

最大子段和

也是十分简单的动态规划问题，可以在leetcode上找到原题，甚至不需要二维表。

分治法的时间复杂度$O(nlogn)$

动态规划法很简单啊，递归式如下：

$b[j]=max{b[j-1]+a[j],a[j]}$

时间复杂度和空间复杂度都为$O(n)$，对于空间复杂度可以化简到$O(1)$

一维的难度并不大，所以书上还给出了矩阵的最大子段和，但是典懒得看书，不如看垃圾CSDN[https://blog.csdn.net/kavu1/article/details/50547401]

上代码：这里也用到了最大子段的代码函数MaxSum

int MaxSum2(int m,int n,int a[M][N])
{
    int sum = 0;
    int *b=new int[n];
    int max=0;
    for (int i=0;i<m;i++){
        for (int k =0;k<n;k++)
            b[k]=0;       
        for(int j=i;j<m;j++){//枚举初始行i,结束行m
            for(int k = 0;k<n;k++)
                b[k] += a[j][k];//b[k]为纵向从行i到行m的之和
            max=MaxSum(n,b);   
            if(max>sum)
                sum=max;
        	}
        	}
    return sum;
}
int MaxSum(int n,int *a)
{
   int sum1=0,b=0;
    for(int i=0;i<n;i++){
        if(b>0){
            b += a[i];
        }else{
            b=a[i];
        }
        if(b>sum1){
            sum1=b;
        }
    }
    return sum1;
}

这样的时间复杂度为$O(mn^2)$，空间复杂度为$O(mn)$，书上还叙述了时间复杂度和空间复杂度分别为$O(m(n-m))$和$O(n)$的算法，就不多说了。

凸多边形的最优三角剖分

这部分可谓是完全没有听。题目就是一个凸n边形，可以通过n-3条弦分成n-2个三角形，现在给弦和边函数和一些数值，使得剖分得到的函数和最小。

十分抽象的是，我们可以把这类问题等价于矩阵连乘问题（这个正常人真想不到）

把矩阵连乘变成树我还是可以理解的，毕竟dp和分治也不能说是没有一点关系，其中同层的节点先乘。但是把树扭一扭就能变成凸多边形属实是想不到的，这东西叫语法树。但是换个角度想，我加一条弦，就是把多边形（边）分成了两部分（子树），之后每部分（子树）继续加弦，就能成为一个二叉树，完全合理。

注意，该问题的递归式和矩阵连乘的递归式是完全相同的

对应的时间复杂度也是类似的$O(n^3)$。但是构造最优三角剖分的时间复杂度为$O(n)$

流水作业调度

我们令S为所有作业N的子集，那么当M1开始加工S中作业时，机器M2还在加工其他作业，到时间t之后才可利用，所以我们描述最短时间为$T(S,t)$，整个流水调度问题的最优解为$T(N,0)$。实际上不难理解，对于一个最优调度，整体的时间等于M1处理第一个任务的时间和M2处理其余所有任务的时间和。关于子结构的性质证明参见书上内容：

实际上，根据它的最优子结构性质，我们也能得到递归式：

$T(N,0)=min_{1\leq i\leq n}(a_i+T(N-{i},b_i))$

通常情况如下：

以上是作为一个动态规划问题的正常算法，但是也没有给代码。

然后书上提到了一个极度让人看不懂的东西：Johnson算法？实际上就是在调度时，相邻的两个任务，如果在这种调度下的时间小于交换这两个任务的之后调度的时间，那么这时候这两个相邻作业是满足Johnson不等式的。所以存在不断地交换相邻任务（逆序对），使得整体的时长最短。所以问题就变成了一个排序问题。时间复杂度为$O(nlogn)$。

说实在的，感觉这道题貌似跟动态规划没有太大关系。Johnson算法如下：

把$a_i<b_i$的任务归给$N_1$，其他的归给$N_2$。对$N_1$升序排序，$N_2$降序排序。就满足了最优调度。

没得说

0-1背包问题

这东西看上去就是个动态规划问题，但是做到这里，也应该怎么证明一个最优子结构性质了。

首先根据问题的描述设一个最优解，取问题和最优解的子集，接着反证，说子问题有另一个最优解，让他和去除的部分结合，结果发现与最优解不相等，所以矛盾了，所以有最优子结构性质。

终于是回归到了正常的动态规划算法，实际上，如果没有背包容量作为限制条件的话其实就是最大子段和问题。基于上述内容，艹，电子书上的递归式有点绕，换一个，就直接创建这样一个表：

二层遍历，时间复杂度为$O(n*m)$但是我不理解啊，为什么书上的这么复杂？完全不懂，摆烂先。

最优二叉搜索树

我开始以为这道题就是构建一颗二叉搜索树，结果发现不是这样的。给定一个集合，我们生成许多个二叉搜索树，使得访问的期望最小。这颗树同样也是满足最优子结构的，但是由于涉及到了递归，所以细节不好说明。

但是思路也是很简单，有点晕，先鸽了，明天继续。

第4章贪心算法

趟过了动态规划之后就没有太大的难度了，接下来就是贪和图论里面的经典操作。

要证明贪心策略和贪心选择有效性。

动态规划具有最优子结构问题，即问题的最优解，将问题取子问题，解取对应的子解同样满足最优，而贪心则意味相反的，在当前（子情况）中最优解就是整体的最优解，这决定了贪心算法并不难，但是对应的，我们需要证明原因。

与动态规划类似，可以使用贪心算法的题目通常具有以下两个性质：贪心选择性质和最优子结构性质。贪心选择性质即目光短浅，只考虑当前情况就可以满足全局最优解。而最优子问题在动态规划中就有提到了。所以说，在某个层面，贪心算法算是动态规划问题的子集。

问题	时间复杂度	备注
活动安排问题	$O(nlogn)$
最优装载	$O(nlogn)$
哈夫曼编码	$O(nlogn)$
最小生成树	P$O(n^2)$ K$O(eloge)$
多机调度问题	$O(nlogn)$

活动安排问题

给出一堆活动，要求安排活动使得尽可能少的天数完成。那就硬贪，贪结束最早的活动。具体算法是花$O(nlogn)$对活动根据结束时间进行升序排序，之后活动不冲突的就丢进去，最后就能得到最多的活动安排。

那么如何说明？在该题中，贪心的意义是使剩余的可安排时间最大化。至于具体而又冗杂的说明，看看书吧：

总而言之，难度不大，时间复杂度为$O(nlogn)$

最优装载问题

承载量为c的轮船，集装箱i的重量为$w_i$，尽可能装多的集装箱。不愧是贪心，容易的一匹。升序排序，丢进轮船。时间复杂度同样为排序的时间$O(nlogn)$

至于性质证明：

哈夫曼编码

哈夫曼编码也是数据结构里面学过的东西，甚至能拿出来在编码论中反复鞭尸。关键是如何说明哈夫曼算法是正确的。

首先证明贪心选择性质：

接下来证明最优子结构

算法的难度确实不大，但是理解证明确实难度不小。

最小生成树

最小生成树是指对图进行剪枝得到路径权值之和最小的树（因为树不存在环）。同样在数据结构中有所涉及。有两个方案：Prim算法和Kruskal算法，两种算法的流程和使用场合也有所不同，需要一一讨论，而且相较于上面的贪心，这个难度更大了一点，所以可能需要熟悉的掌握了。

设$G=(V,E)$是无向连通带权图。上述的两个算法都是做了贪心，虽然凡是不同，但是都利用了MST性质，即对于U为V的真子集，若有$(u,v)\in E$且$u\in U, v\in V-U$，在所有的边中，$(u,v)$的权最小，那么一定存在$G$的一颗最想生成树，以$(u,v)$为其中一条边。证明如下：

基于上述的MST，接下来康康Prim和Kruskal算法的步骤。

Prim算法：不断选择最短的边，直到所有的点均包含在图中。（贪在选最短边）但是实现的过程中稍微有点要考虑的是如何找到满足$i \in S和j\in V-S$两个条件的边。首先把一个节点作为起点放到列表里，之后找到该节点所连接的所有节点以及对应的边，取最小的边添加到边数组中，同时节点也添加回到列表中。（BFS）所以整体的复杂度为$O(n^2)$

书上的源码是正经做法，实际上我们也在数据结构中学到过使用队列的代码：

至于基于优先队列的实现可以看看这个：https://blog.csdn.net/qq_37497322/article/details/75043491

Kruskal算法Kruskal的算法则是直接找图最小的边，直到生成一棵最小生成树。同样可以整个优先队列来玩。

时间复杂度是$O(eloge)$，其中将边按权组成优先队列需要$O(e)$的时间，while循环中的需要$O(loge)$时间，所以整体就是一个乘积。

根据两者的时间复杂度来看，需要根据不同的情况使用不同的算法来取得最好的时间损耗。当$e=\Omega(n^2)$时，Kruskal算法比Prim算法差，但是当$e=O(n^2)$时，Kruskal算法比Prim算法好得多。

多机调度问题

NP完全问题，无有效解法，所以使用贪心选择策略设计较好的近似算法。

使用最长处理时间作业优先的的贪心选择策略，没有证明，也不算很难，时间复杂度为$O(nlogn)$

至此就完成了贪心算法的一个说明，难度不大，但是涉及到证明还是需要好好看看。那就再看看贪心策略的证明方案吧.

贪心正确性证明

贪心的正确性证明有一个方法叫做：Exchang Arguement，交换参数，该方法的核心思想就是：假设存在一个最优算法和我们的贪心算法接近，之后交换算法中的一个步骤或元素，得到一个新的最优算法，且该算法比前一个最优算法更接近我们的贪心算法从而得到矛盾，说明我们的贪心算法是正确的。

很绕，举个例子：以活动安排问题为例。首先贪心算法就是排序，把结束时间最早的加入活动列表，我们叫这个算法（贪心）为A。假设A不是最优的，那就一定存在一个算法O，其和A最相近（前k-1个选择相同，第k个不同），也就是说，原本算法A的第k个选择是$(a_i,b_i)$而算法O的第k个选择是$(a_j,b_j)$，根据我们对A的定义，可以知道$b_i<=b_j$。那么我们构造一个$O’=O-(a_j,b_j)+(a_i,b_i)$

那么这个$O’$有两个性质：1、没有重叠。$O’$中的前k-1个元素和A一样而k之后的元素和O一样，且由于$b_i<=b_j$所以未发送冲突。2、$O’$是一个最优解，因为它的元素个数和O是一样的。

至此就找到了最优解$O’$与A具有K个共同的元素，但是这与我们之前的假设冲突了，所以A最优。

同理，其他的算法也是类似的原理，可以参考着试一下。

第5章回溯法

回溯法和下一章的分支界限法是有点关系的，回溯法主要使用了DFS，即一次得到一个结果，获取所有结果。就像每一章都会有对应的重点一样，这章的重点不是暴力搜索和建树，而是判断终止条件。

问题	时间复杂度	备注
装载问题	不记录$O(2^n)$，记录可以$O(2^n)和O(n2^n)$
批处理作业调度	$O(n!)$
符号三角形问题	$O(n2^n)$
n后问题	$O(n!)$
最大团问题	$O(n2^n)$
旅行售货员问题	$O(n!)$

在解决问题时，回溯有两个方案。一个是基于递归的，也是比较喜欢的方案：

另一个则是基于迭代的（也可以叫做非递归写法）

装载问题

首先要注意的是，这里的装载问题只有两艘船，属于第4章题目的特殊情况，同时又可以看作是0-1背包问题。

这一道题给出了4种代码，我们直接看带记录的：

不带记录的话时间复杂度为$O(2^n)$，带记录的话时间复杂度为$O(n2^n)$但是也可以通过一些方法把时间复杂度降到$O(2^n)$。分别为得到最优解后重新访问得到节点和动态更新最优解。

本题中的终止条件为cw+w[i]>=c即对于一个新的货物，当放到船1上的时候，如果放的下，则继续对船一放置货物（左子树），否则向船二放置（右子树）。

除了上述的方法以外还有一种迭代的回溯法，当然时间复杂度是不变的，但是可能会更加恶心一点。

批处理作业调度

前面没有提到的是，对于回溯法问题，通常由两种典型的解空间树，分别为子集树和排序树。当问题为从集合中找到满足某个性质的子集时，称解空间树为子集解。当问题是确定n个元素满足某种性质的排序时，解空间是排列树。上题即为子集树，而该题为排序树。

子集树的框架：

搜索树的框架：

批处理作业调度问题指的是一堆任务和两个机子，每个作业都要先机器1完成之后机器2完成。每个任务对两个机子的运行时间不同。可以证明，只有两个机子完成的顺序相同时时间最短。

看到这里，首先要澄清一下这道题和dp中流水作业算法的关系。该题目的目的是求n个作业的最小完成时间之和，就是操作系统中的那个概念。而流水作业则是所有任务完成消耗的时间。

愚蠢的回溯法啊，就是暴力列举出所有可能的情况以及对应的结果，找到和最小的就好了。所以时间复杂度为$O(n!)$

由于该题目是一个排序树，其终止条件是递归地层数达到排序元素的个数，即j<=n

符号三角形问题

给定一个符号数n，生成一个符号三角形，其中两个同号下为+，异号下为-，找到所有+和-符号个数相同的情况：

怎么个做法？实际上可以通过一颗二叉树实现，对于两种符合号，假设左子树为+，右子树为-，那么n个符号，最后的叶子就有$2^n$个，那么这$2^n$个叶子，但是实际上，为了保证生成的树+和-的数量相等，我们需要最后生成的符号三角中两种符号的数量都不超过$\frac{n(n+1)}{22}$。此外为了进一步简化复杂度，我们不难得知，当我们确定了前i个字符之后，接下来只需要斜着添加一行就是i+1个字符的符号三角形了。在回溯过程中，以两种符号的个数都不超过$n(n+1)/4$为可行性约束并减去子树，且当$n(n+1)/2$为奇数时不存在数量相同的符号三角形，基于上述条件核心的代码如下：

其中t表示层，count为+的数量，half即为$n*(n+1)/4$，sum表示符号三角数量。终止条件即为count>half（+的数量）或是（-的数量）超过half。时间复杂度为$O(n2^n)$。感觉不会很乐意考

n后问题

n个棋子放在n*n的棋盘上，每行每列没斜线不能出现多个皇后。算是一个排序树吧。

其中的place函数即为终止条件的判断，判断是否在一条线上。其中x为当前解的数组，t为递归深度。可以这样理解，每一层递归都对应着期棋盘的一行，x记录了每一行皇后的位置，所以判断的时候只需要看看有无同列即可（x[j]==x[k]）。而abs(k-j)==abs(x[j]-x[k])则判断有无同对角线。对应的时间复杂度为$O(n!)$

0-1背包问题

可恶，拿一道题反复鞭尸，不讲武德。0-1背包问题是NP完全问题，而且是解空间树是子集树，相较于dp，其实更容易理解，即左子树放，右子树不放，暴力列举所有情况，然后计算叶子节点的价值即可。为了加速算法，可以首先对物品进行降序排序。

终止条件可以有两个，一个很简单，就是当超出背包容量的时候剪枝，另一个就是当前物品的价值大于最优价值时对右子树剪枝。分别对应着cw+w[i]<=c和Bound(i+1)>bestp

时间复杂度为$O(n2^n)$

最大团问题

还是一个子集选取问题，还是子集树，所以复杂度就不用多说了$O(n2^n)$。左子树即为连通点，右子树需要确认有足够多的可选择顶点。

因此终止条件也就是对应的，不是很想整理这道题。

旅行商售货问题

好家伙连题都不给了，但是这是一个排序树，所以复杂度是$O(n!)$。

第6章分支界限法

如果说第五章是DFS，那么第六章就是BFS，尽可能快的找到最优解。通常使用队列实现，也正是因为如此，队列可能为本章的主要考核，除此之外还有树的生成和遍历。好在本章的内容并不多。

问题	时间复杂度	备注
最优装载	$O(2^n)$

分支界限法的核心就是尽可能的伸出多个解，当找到一个解的时候所有分支全部中断，其最大的好处在于代码很容易看懂（xs）直接上题目吧：

装载问题

老牌问题，通常BFS是来找距离最近的解的方案，但是这道题也确实可以这样用（实际上就是BFS暴搜）。康康代码：

对于一个起始的节点，把所有的放到队列里面，接下来取出来，遍历所有边，把符合条件（能承载下）的结点放到队列里，接下来继续。这道题之所以可以使用这个方案的另一个原因是图不存在环。时间复杂度是$O(2^n)$。

除此之外还有基于优先队列的分支界限法。与上述方法不同，优先队列首先将数据进行排序以生成最大最小，该题目中的优先级定义为根节点到节点x的路径相应的载重量再加上剩余集装箱的重量之和

算法设计与分析

第1章 算法概述

NP完全性理论

第2章 递归与分治策略

递归的概念

分治法的基本思想

二分搜索

大数乘法

Strassen矩阵乘法

棋盘覆盖

合并排序

快速排序

线性时间选择

最近点对问题

第3章 动态规划

矩阵连乘问题

最长公共子序列

最大子段和

凸多边形的最优三角剖分

流水作业调度

0-1背包问题

最优二叉搜索树

第4章 贪心算法

活动安排问题

最优装载问题

哈夫曼编码

最小生成树

多机调度问题

贪心正确性证明

第5章 回溯法

装载问题

批处理作业调度

符号三角形问题

n后问题

0-1背包问题

最大团问题

旅行商售货问题

第6章 分支界限法

装载问题

第1章算法概述

第2章递归与分治策略

第3章动态规划

第4章贪心算法

第5章回溯法

第6章分支界限法