【算法】代码随想录

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

本文同时参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

该文章记录着我本学期 "算法设计与分析" 这一门课程的学习历程~

1. 归纳🍺

1.1 选择排序

时间复杂度：

O(n^2)

public static void main(){
    selectSort(1,n,A);
}

private static void selectSort(s,t,A){ // 对A[s..t]按升序选择排序
    if(s<t){
        k=s;
        for(j=s+1 to t){	// 选出A[s..t]中最小元素
            if(A[j]<A[k])
            k=j;
        }
        if(k!=s)
            A[s]<->A[k];	// 交换A[s]、A[k]
        selectSort(s+1,t,A);// 对A[s+1..t]按升序选择排序
    }
}
复制代码

1.2 插入排序

时间复杂度：

O(n^2)

public static void main(){
    insertSort(1,n,A);
}

private static void insertSort(s,t,A){ // 对A[s..t]按升序插入排序
    if(s==t){
        return;        
    }else{
        insertSort(s,t-1,A);	// 对A[s..t-1]按升序插入排序
        x=A[t];
        j=t-1;
        while(j>0&&A[j]>x){
            A[j+1]=A[j];
            j=j-1;            
        }
        A[j+1]=x;
    }
}
复制代码

1.3 整数幂问题

组合求解

时间复杂度：

O(n·logn)

public static void main(){
    power(x,m);
}

private static double power(x,m){
    if(m==0)
        return 1;
    else{
        y=power(x,m/2);
        y=y*y;
        if(m%2!=0)
            y*=x;
        return y;
    }
}
复制代码

1.4 棋子移动游戏

时间复杂度：

O(n)

public static void main(){
    chessMove(n);
}

private static void chessMove(n){
    if(n==4){
        // Ⅰ
        move(4,9);
        move(5,10);
        // Ⅱ
        move(8,4);
        move(9,5);
        // Ⅲ
        move(2,8);
        move(3,9);
        // Ⅳ
        move(7,2);
        move(8,3);
        // Ⅴ
        move(1,7);
        move(2,8)
    }else{
        // 第一组动作
        move(n,2n+1);
        move(n+1,2n+2);
        // 第二组动作       
        move(2n-1,n);
        move(2n,n+1);
        chessMove(n-1);	// 递归求解 n-1 子问题
    }
}
复制代码

1.5 多项式求值

求解多项式：

P_n(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0（数组长度为\ n+1）

时间复杂度：

O(n)

public static void main(){
    // 注意 n 的初始值为 0
    horner(A,0,x);
}

private static int horner(A, n, x) {
    // A.length 的值为 n+1
    if (n == A.length - 1) {
        return A[n];
    } else {
        return x * horner(A, n + 1, x) + A[n];
    }
}
复制代码

1.6 寻找多数元素

归纳法求解

时间复杂度：

O(n)

public static void main(){
    c = candidate(1);
    count = 0;
    for(int j=1; j<=n; j++)
        if(A[j]==c)
            count++;
    if(count>n/2)
        return c;
    else
        return null;
}

/**
 * n个元素的数组：A[1...n]
 */
private static int candidate(m){
    j = m;
    c = A[m];
    count = 1;
    while(j<n && count>0){
        j++;
        if(A[j]==c)
            count++;
        else
            count--;
    }
    if(j==n)
        return c;
    else
        return candidate(j+1);
}
复制代码

1.7 生成全排列

时间复杂度：

O(n·n!)

注意：不要存储全排列；元素交换后需要换回以保持原状态！

public static void main(){
    // P[1...n] 存放每一个排列
    for(int j=1; j<=n; j++)
        P[j] = j;
    permutation1(1);
}

// 时间复杂度：O(n·n!)
private static int permutation1(m){
    if(m==n)
        System.out.println("P[1...n]");
    else{
        for(int j=m; j<=n; j++){
            swap(P[j],P[m]);
            permutation1(m+1);
            swap(P[j],P[m]);	// 输出后不存储，立即换回以保持原状态
            // 此时 P[m...n] 为 m, m+1, ..., n
        }
    }
}
复制代码

2. 分治法🐱‍👤

2.0 快速排序

时间复杂度：

O(n·logn)

空间复杂度：

O(1)

void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); // 将中间的这个数和第一个数交换
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                s[i++] = s[j];
            
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        // 分治
        s[i] = x;
        quick_sort(s, l, i - 1); 	// 递归调用 
        quick_sort(s, i + 1, r);
    }
}
复制代码

2.1 归并排序

输入：n 个元素的数组

A[1...n]

时间复杂度：

O(n·logn)

空间复杂度：

O(n)

public static void main(){
    mergeSort(A, 1, n);
}

private static void mergeSort(A, low, high){
    // 将 A[low...high] 按非降序归并排序
    if(low < high){
        mid = (low+high)/2;			// 分解~
        mergeSort(A, low, mid);		// 左递归
        mergeSort(A, mid+1, high);	// 右递归
        merge(A, low, mid, high);	// 合并~
    }
}

private static void merge(A, low, mid, high){
    // 将 A[lo...mid] 和 A[mid+1...hi] 归并
    int i = low, j = mid + 1;

    for (int k = low; k <= high; k++)
        // aux[]: 归并所需的辅助数组（空间复杂度的由来）
        aux[k] = A[k];

    for (int k = low; k <= high; k++) {
        if (i > mid)
            A[k] = aux[j++];
        else if (j > high)
            A[k] = aux[i++];
        else if (aux[j] < aux[i])
            A[k] = aux[j++];
        else
            A[k] = aux[i++];
    }
}
复制代码

2.2 大整数乘法

解法 1：分治法

使用分治算法，可以将上界显著缩小，为简单起见，假定 n 是 2 的幂，算法思路如下：

把每个整数分为两部分，每部分分为 n/2 位，则 u 和 v 可重写为

u = w2^\frac{n}{2} + x

v = y2^\frac{n}{2} + z

u = w2^\frac{n}{2} + x

w（高位）	x（低位）

v = y2^\frac{n}{2} + z

y（高位）	z（低位）

u 和 v 的乘积可以计算为：

$uv = (w2^\frac{n}{2} + x)(y2^\frac{n}{2} + z) = wy2^n + (wz + xy) 2^n/2 + xz$

该分治算法的时间复杂度

T(n)

满足：

T(n)=\begin{cases} 1 & ,n=1\\ 4T(\frac{n}{2})+bn & ,n>1 \end{cases}

时间复杂度：

T(n) = O(n^2)

解法 2：算法改进

wz + xy = ( w + x )( y + z ) - wy - xz

于是，最终运算式：

uv = wy2^n + (( w + x )( y + z ) - wy - xz) 2^\frac{n}{2} + xz

这样 u 和 v 的乘法运算简化为 3 次 n/2 规模整数的乘法运算和 6 次加减运算，这些加减所化时间是

Θ(n)

；此方法产生以下递推式：

T(n)=\begin{cases} d & ,n=1\\ 3T(\frac{n}{2})+bn & ,n>1 \end{cases}

时间复杂度：

T(n)=O(n^{log_2{3}})\approx O(n^{1.59})

2.3 矩阵乘法

问题描述：设 A、B 为 n 阶方阵，求解

C = AB

C(i,j)=\sum A(i,k)B(k,j)

解法 1：简单递归法

假定

n = 2^k

n/2 * n/2

$的子矩阵：$

A = \left( \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right) \ B = \left( \begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} \right) \ C = \left( \begin{matrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{matrix} \right)

用分治方法来计算 C 的组成，由以下等式定义：

C = \left( \begin{matrix} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\ A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22} \end{matrix} \right)

可得

C = AB

$需要 8 次$

n/2

阶方阵乘法，4 次

n/2

阶方阵加法。

设

a

和

m

分别表示一次数量加法和乘法的时间，则该算法的递推式为：

T(n)=\begin{cases} m & , n=1 \\ 8T(\frac{n}{2})+an^2 & , n>1 \end{cases}

时间复杂度：

T(n)=O(n^3)

由此可见，分治算法不产生有效的算法，相反，它耗费的时间比传统方法多，增加的时间和空间的耗费来自递归带来的管理开销。换句话说，这只不过是传统方法的递归形式，两种算法的区别仅仅在于矩阵元素相乘的次序上。

解法 2：STRASSEN 算法

时间复杂度：

O(n^{log7})\approx O(n^{2.81})

2.4 寻找第 k 小元素

时间复杂度：

O(n)

随机化的线性选择算法

s=select(A,1,n,k);

select(A,low,high,k){
    // 求A[low..high]中的第k小元素并返回
    p=high-low+1;	// p为当前处理的元素个数
    if(p<44){		// 当元素个数<44时，直接求解
        // 讲 A[low..high] 排序
        sort(A[low..high]);
    	return (A[low+k-1]);
    }
    // 以下分解子问题
    q=⌊p/5⌋;
    // 将 A[low..low+5q-1]分为q组，每组5个元素，将q组中的每一组单独排序并找出中项，所有的中项存于数组M[1..q]中
    mm=select(M,1,q,⌈q/2⌉);		// 求中项序列M的中项mm
    // 将 A[low..high] 分为三组
    A1={a|a<mm};
    A2={a|a=mm};
    A3={a|a>mm};
    // 以下选择一个子问题递归或直接求解
    case{
        |A1|>=k:
        	return select(A1,1,|A1|,k);
        |A1|+|A2|>=k:
        	return mm;
        |A1|+|A2|<k:
        	return select(A3,1,|A3|,k-|A1|-|A2|);
    }
    
}
复制代码

2.5 最近点对问题

算法思路：将 S 分成不相交的两个子集，求每个子集的最近点对，以及分别位于两个子集中的所有点对的最近点对，最后通过比较得到 S 中的最近点对

时间复杂度：

T(n)=O(nlogn)

分治法

// 我赌你的枪里没有子弹
复制代码

3. 动态规划🐙

引例：Fibonacci

解法 1：迭代算法

fd(n)
    if(n==1 or n==2)
        return 1;
	else{
        x=1;
        y=1;
        for(i=3 to n){
            z=x+y;
            x=y;
            y=z;
        }
        return z;
    }
End fd
复制代码

解法 2：基于记忆的递归（动态规划）

Fibonacci(n)
    if(a[i]==-1){
        if(i==1 or i==2)
            a[i]=1;
        else
            a[i]=Fibonacci(i-1)+Fibonacci(i-2);
    }else{
        return a[i];
    }
End Fibonacci
复制代码

3.1 矩阵链乘问题（填表）

时间复杂度：

O(n^3)

空间复杂度：

O(n^2)

3.1.1(1) 解法 1：自顶向下的递归算法（求解最优值）

public static void main(){
    MM(r,1,n);
}

// 初始c[][]=-1 表示该值未求，且第i个矩阵的的行列值为 r[i], r[i+1]
private static int MM(r[],j,k){
    if(j==k)		// 只有一个矩阵~
        return 0;
    else if(c[j,k]!=-1)		// 该值存在(子问题已被标记过)，可直接返回！(提高效率)
        return c[j,k];
    
    minV = MAX_INT;
    for(int i=j+1; j<=k; j++){	// 加括号位置枚举
        t = MM(j,i-1) + MM(i,k) + r[j]*r[i]*r[k+1];
        minV = min(r,minV);
    }
    c[j,k]=minV;
    return c[j,k];
}
复制代码

3.1.1(2) 解法 2：自底向上的迭代算法（求解最优值）

public static void main(){
    // 输入: 矩阵个数n,阶r[1..n+1],其中r[k]、r[k+1]分别为第k个矩阵的行列值
    // 输出: n个矩阵相乘的乘法最小次数，最优顺序的信息数组S[1..n, 1..n]
    Matchain();
}

private static ... Matchain(){
    for(int i=1; i<=n; i++)
        C[i,i]=0;		// 设置对角线为0
    for(d=1 to n-1){		// 逐条计算对角线d(1)~d(n-1)
        for(i=1 to n-d){	// 计算对角线d的n-d个元素
            j=i+d;
            c[i,j]=MAX_INT;
            for(k=i+1 to j){
                x = C[i,k-1] + C[k,j] + r[i]*r[k]*r[j+1];
                if(x<C[i,j]){
                    C[i,j]=x;		// 更新值
                    S[i,j]=k;		// 记录分割位置
                }
            }
        }
    }
    
    return C[1,n], S;
}
复制代码

3.1.2 最优乘法顺序（构造最优解）

输入：矩阵数

n,M_1,M_2,...,M_n

S[1..n,1..n]

输出：按最优顺序计算的矩阵链乘积

M=M_1M_2...M_n

// 调用 M=matchain_product(1,n);
matchain_product(i,j){	// 求按最优顺序计算的矩阵链乘积 M[i]M[i+1]...M[j]
    if(i==j)
        return M[i];
    else{
        A=matchain_product(i,S[i,j]-1);
        B=matchain_product(S[i,j],j);
        C=multiply(A,B);		// 计算两个矩阵乘积 C=AB
        return C;
    }
}
复制代码

3.2 最长公共子序列问题（填表）

3.2.1 LCS 迭代算法：求解最长公共子序列的长度（求解最优值）

LCS 时间复杂度：

Θ(nm)

LCS 空间复杂度：

Θ(nm)

输入：

n、m、A=a_1a_2...a_n、B=b_1b_2...b_n

输出：A 和 B 的 LCS 长度

L[n, m]

和存储 LCS 有关信息的数组

H[1..n, 1..m]

private static ... LCS(){
    // 初始化边缘~
    for(i=0 to n)
        L[i,0]=0;
    for(j=0 to m)
        L[0,j]=0;
    
    for(i=1 to n){
        for(j=1 to m){
            if(a[i]==b[j]){
                L[i,j]=L[i-1,j-1]+1;
                H[i,j]=0;
            }else{
                if(L[i-1,j]>=L[i,j-1]){
                    L[i,j]=L[i-1,j];
                    H[i,j]=1;
                }else{
                    L[i,j]=L[i,j-1];
                    H[i,j]=2;
                }
            }
        }
    }
    // 返回相关信息(H用于LCSS算法)
    return L[n,m], H;
}
复制代码

3.2.2 LCSS 迭代算法：构造最长公共子序列（构造最优解）

H[i,j]=0

a_i

$，并前进到$

H[i-1,j-1]

(C包含a_i)

H[i,j]=1

H[i-1,j]

(C不包含a_i)

H[i,j]=2

H[i,j-1]

(C不包含b_i)

private static int[] LCSS(){
    C=[]; i=n; j=m;
    while(i>0 && j>0){
        if(H[i,j]==0){
            C=a[i]+C;	// 遇到转折点即逆序追加~
            i=i-1;
            j=j-1;
        }else{
            if(H[i,j]==1){
                i=i-1;
            }else{
                j=j-1;
            }
        }
    }
    
    return C;
}
复制代码

3.3 嵌套矩形问题

3.3.1 求解最优值

时间复杂度：

O(n+e)

空间复杂度：

O(n^2)

public static void main(){
    // d[1..n]保存各个顶点在DAG中的最长路径长度
    c=BuildGraph();		// 构造邻接矩阵c
    for(i=1 to n)		// 初始化，d[i]均未求
        d[i]=-1;
    for(i=1 to n)
        d[i]=maxlength(i);
    max=d[1];
    // 从各个顶点出发的最长路径中找到DAG的最长路径~
    for(i=1 to n)
        if(max<d[i])
            max=d[i];
    
    return 1+max;
}

// 在 DAG 中计算i的最长路径长度
private static int maxlength(i){
    if(d[i]>-1)
        return d[i];	// d[i]已经求出，直接返回
    // 若未求过d[i]，则从其后继节点中找寻最长路径
    max=0;
    for(j=1 to n){
        if(c[i,j]>0){	// 顶点j为顶点i的后继
            x=maxlength(i);		// 求顶点j的最长路径长度
            if(max<1+x)
                max=1+x;
        }
    }
    d[i]=max;
    return d[i];
}
复制代码

3.3.2 构造最优解

输入：n 个矩形

输出：n 个矩形最多可以嵌套的个数

//数组 d[1,..,n] 保存各个顶点在 DAG 中的最长路径长度
Nested_Rectangle_Rec(){
    c=BuildGraph();		// 构造DAG，得到邻接矩阵c
    for(i=1 to n)
        d[i]=-1;
    for(i=1 to n)
        // 从各个点出发的最短路径长度
        d[i]=maxlength(i);
    max=d[1];
    for(i=1 to n){
        if(max<d[i])
            max=d[i];
    }
    return 1+max;
}
复制代码

3.4 0/1 背包问题（填表）

3.4.1 求解最优值

时间复杂度：

求最优值（迭代）： $O(n·C)$
求最优解（递归）： $Θ(n)$

空间复杂度：

O(n·C)

public static void main(){
    KnapsackRec();
}

// 背包问题的初始化
private static ... KnapsackRec(){
    for(i=0 to n)
        for(j=0 to C)
            V[i,j]=-1;	// 所有的值均为被求解过~
    maxV = knapsack(n,C);
    return maxV, H;
}

/**
 * 求解背包问题
 * 设有一容量为C的背包，n个物品的集合U={u1,u2,..,un}，物品u[j]的体积和价值分别为s[j]和v[j]
 * V[i,j]的i表示可选物品，j表示容量，V[i,j]值表示价值
 * 最优解的相应信息存入数组H[0..n, 0..C]
 *		H[i,j]=1，表示求解V[i,j]对应的子问题时 将物品 u[i]装入背包~
 *		H[i,j]=0，表示求解V[i,j]对应的子问题时不将物品 u[i]装入背包~
 */
private static void knapsack(i,j){
    // 相应的子问题未求解过
    if(V[i,j]==-1){
        if(i==0||j==0){
            // 容量不足或已无物品(到边界)
            V[i,j]=0;
        }else if(s[i]>j){
            // 容量不足以放入物品u[j]，同样选择不放入
            V[i,j]=knapsack(i-1,j);
            H[i,j]=0;
        }else{
            a1 = knapsack(i-1,j-s[i])+v[i];
            a2 = knapsack(i-1,j);
            if(a1>a2){
                V[i,j]=a1;
            	H[i,j]=1;
            }else{
                V[i,j]=a2;
                H[i,j]=0;
            }
        }
        
    }else{
        // 已存在该值，无需重复求解
        return V[i,j];
    }
}
复制代码

3.4.2 构造最优解

利用最优解的信息数组 H，从最后一个分量开始向前递推求最优解

(x_1,x_2,...,x_n)

当

H[i,j]=1

V[i,j]

对应的子问题时将物品

u[i]

装入背包
当

H[i,j]=0

V[i,j]

对应的子问题时不将物品

u[i]

装入背包

输入：n，C，体积

s[1..n]

，最优解信息

H[0..n,0..C]

输出：相应的 0/1 背包问题的剩余容量

private static int[] Knapsack_solution(){
    // y表示当前背包的剩余容量~
    y=C;
    X[n]=H[n,C];
    for(i=n to 2){
        // 如果标志为装入，则从背包从减去对应的物品容量大小
        if(X[i]==1)
            y=y-s[i];
        // 递归求解剩余最优解~
        X[i-1]=H[i-1,y];
    }
    return X;
}
复制代码

4. 贪心算法🔥

4.1 Prim 算法

 Prim(){
     T=∅;
     x={1},Y=V-{1};	// 从V1开始遍历
     
     while(T!=∅){
         从{(u,v)|u∈X,v∈Y}中选出最小权值的边(x,y);
         
         X=X∪{y};	// 从集合X中加入点y
         Y=Y-{y};	// 从集合Y中删除点y
         T=T∪{(x,y)};	// 向最小生成树的边集中添加边(x,y)
     }
 }
复制代码

4.2 Huffman 算法

另见博客：blog.csdn.net/fx677588/ar…

4.3 有期限的作业安排问题

另见博客：blog.csdn.net/qq_45815776…

4.4 分数背包问题

时间复杂度：

Θ(nlogn)

输入：表示背包容量的实数

C

，物品数

n

，表示 n 个物品的体积和价值的实数数组

s[1..n]

和

v[1..n]

输出：装入背包物品的最大总价值

maxv

和相应的最优解

x[1..n]

/**
 * 数学模型：z = max{v1x1+v2x2+...+vnxn}
 * 
 * xi 表示物品i装入背包的部分占该物品全部的比例(0<=xi<=1)
 */
Greedy_Knapsack(){
    for(i=1 to n)
        y[i] = v[i]/s[i];	// 求n个物品的单位体积价值
    
    // 对y[1..n]按降序地址排序，排序结果返回到数组d[1..n]中，使得 y[d[1]]>=y[d[2]]>=...>=y[d[n]]
	d=sort(y,n);
    for(i=1 to n)
        x[i]=0;		// 对x[1..n]初始化
    i=1; maxv=0; rc=C;	// 以下rc表示当前背包的剩余容量
     
    while(rc>0 && i<=n){
        j=d[i];		// u[j]为当前考虑选择的物品
        if(s[j]<=rc){
            // 选择物品u[j]全部装入背包
            x[j]=1;
        	rc=rc-s[j];
        }else{
            // 选择物品u[j]的一部分将背包填满
            x[j]=rc/s[j];
            rc=0;
        }
        maxv=maxv+v[j]*x[j];
        i=i+1;
    }
    
    return maxv,x[1..n];
}
复制代码

4.5 多机调度问题

时间复杂度：

Θ(max\{nlogn, nm\})

输入：作业数

n

，机器数

m

，表示

n

个作业所需的处理时间的整数数组

t[1..n]

，表示第

j

台机器被占用的时间

f[1..m]

输出：在

m

台机器上处理

n

个作业所需的近似最短时间

mint

MMJA(){
    f[1..m]=0;
    
    // 对t[1..n]按降序地址排序，排序结果返回到数组a[1..n]中，使得 t[a[1]]>=t[a[2]]>=...>=t[a[n]]
	a=sort(t,n);
    for(i=1 to n){
        j=min(f,m);			// 求f[1..m]的最小值对应的下标
        f[j]=f[j]+t[a[i]];
    }
    mint = max(f,m);	// 求f[1..m]的最大值（即多机调度的最优近似值，取最大值——木桶原理）
    
    return mint;
}
复制代码

4.6 活动安排问题

贪心选择策略：按活动结束时间从早到晚安排活动，每次选择与已选出的活动相容的结束时间尽可能早的活动。

局部最优性：每次为资源留下尽可能多的时间以容纳其他活动。

时间复杂度：

Θ(nlogn)

/**
 * 活动数n,表示n个活动起始时间和结束时间的数组s[1..n]和f[1..n]
 */
Activity_Arrangement()
    
    // 对f[1..n]按升序地址排序，排序结果返回到数组d[1..n]中，使得f[d[1]]<=f[d[2]]<=..<=f[d[n]]
    d=sort(f,n);
    A={d[1]};
	j=d[1];		// 以下j总是表示当前集合A中结束最晚的活动
	for(i=2 to n){
        if(s[d[i]]>=f[j]){
            A=A+{d[j]};		// 在A中加入活动d[i]
            j=d[j];
        }
    }
	return A;

end Activity_Arrangement
复制代码

5. 回溯法🌊

5.0 回溯算法模板

状态空间（解的形式）
约束条件
状态转移

设问题的解空间为

A=\{(x_1,x_2,...,x_n)|x_i∈X_i,i=1,2,...,n\}

形式递归算法
形式迭代算法

5.0.1 求所有解的递归算法

void advance2(k){
    // 在已求得的部分解(x1,x2,..,xk-1)固定的情况下，求问题的所有解并输出
    for(i=1 to n_k){		// n_k为X_k的元素个数
        x[k]=Xk集合中的第i个元素;
        if((x1,x2,...,x_k)满足解的约束条件){
            if(k==n){
                output(x[1..n]);
            }else{
                advance2(k+1);
            }
        }
    }
}
复制代码

5.0.2 求一个解的递归算法

boolean advance1(k){
    // 在已求得的部分解(x1,x2,..,xk-1)固定的情况下，求问题的一个解即可
    for(i=1 to n_k){		// n_k为X_k的元素个数
        x[k]=Xk集合中的第i个元素;
        if((x1,x2,...,x_k)满足解的约束条件){
            if(k==n){
                output(x[1..n]);
                return true;
            }else{
                t=dvance1(k+1);
                if(t)	return true;
            }
        }
    }
    return false;
}
复制代码

5.0.3 求所有解的迭代算法

void BackTrackiter2(){
    k=1;
    x1=X1集合中的第一个元素的前一个元素;
    while(k>=1){
        while(Xk集合未被穷举){
            x[k]=Xk集合中的下一个元素;
            if(满足约束){
                if(k==n){
                    output(x[1..n]);
                }else{
                    k=k+1;	// 前进
                    x[k]=Xk集合中的第一个元素的前一个元素;
                }
            }	// 否则，剪枝
        }
        k=k-1;	// 回溯
    }
}
复制代码

5.0.4 求一个解的迭代算法

void BackTrackiter2(){
    flag=false;
    k=1;
    x1=X1集合中的第一个元素的前一个元素;
    while(k>=1 && !flag){
        while(Xk集合未被穷举 && !flag){
            x[k]=Xk集合中的下一个元素;
            if(满足约束){
                if(k==n){
                    output(x[1..n]);
                    flag=true;
                }else{
                    k=k+1;	// 前进
                    x[k]=Xk集合中的第一个元素的前一个元素;
                }
            }	// 否则，剪枝
        }
        k=k-1;	// 回溯
    }
}
复制代码

5.1 子集生成

解法 1：增量构造法

// 调用：subset1(1)

void subset1(k){
    for(i=1 to k)
        output(A[k]);	// 打印当前集合
    // 对整颗树的根结点做特殊处理
    if(k==1)
        s=1;
    else
        s=A[k-1]+1;	// 确定当前结点往下扩展的最小可能值
    for(i=s to n){
        A[k]=i;
        subset1(k+1);	// 递归构造子集
    }
    
}
复制代码

解法 2：位向量法

void subset2(k){
    if(k==n+1){		// 此时B[1..n]都已经被赋值了
        for(i=1 to k){
            if(B[i]) output[i];
        }
    }
    B[k]=1;	// 选取第k元素
    subset2(k+1);
    B[k]=0;	// 不选取第k元素
    subset2(k+1);
}
复制代码

5.2 八皇后问题

place.java

boolean place(k){
    // 判断第k行皇后是否与前k-1行皇后冲突
    i=1;
    while(i<k){
        if(x[i]==x[k] or |i-k|==|x[i]-x[k]|)
            return false;
        else 
            i=i+1;
    }
    return true;
}
复制代码

解法 0：(求所有解的)枚举法（递归）

// 调用:nqueenBruteForce(1);

void nqueenBruteForce(k){
    // 在前k-1行已放置k-1个皇后的情况下
    for(i=1 to n){
        x[k]=i;	//试着将第k行的皇后放置在第i列位置
        
        if(k==n){	// 找到一个n皇后的排列方式
            if(place()){
                // 无冲突则输出
                output(x[1..n]);
            }
        }else{
            // x[1..k]只是皇后的部分排列
            t1=nqueenBruteForce(k+1);	// 递归，从第k+1行起继续排列皇后
        }
    }
}
复制代码

解法 1：(求所有解的)枚举法 + "剪枝"（递归）

void nqueen2(k){
    // 在前k-1行已放置k-1个皇后的情况下
    for(i=1 to n){
        // 试着将第k行的皇后放置在第i列位置
        x[k]=i;
        // 第k行放置后立马判断是否冲突（冲突则剪枝）
        if(place(k)){
            if(k==n){
                // 无冲突则输出
                output(x[1..n]);
            }else{
            	nqueen2(k+1);
        	}
        }
    }
}
复制代码

解法 2：(求一个解的)递归

boolean nqueen3(k){
    // 在前k-1行已放置k-1个皇后的情况下
    for(i=1 to n){
        // 试着将第k行的皇后放置在第i列位置
        x[k]=i;
        // 第k行放置后立马判断是否冲突（冲突则剪枝）
        if(place(k)){
            if(k==n){
                output(x[1..n]);
                // 找到一个解输出后即返回
                return true;
            }else{
                boolean t = nqueen3(k+1);
                if(t) return true;
            }
        }
    }
    // 无解
    return false;
}
复制代码

解法 3：(求所有解的)迭代

void NQueen1(n){
    k=1;
    x[1]=0;
    while(k>=1){
        while(x[k]<n){
            x[k]=x[k]+1;
            if(place(k)){	// 也可起到剪枝的效果
                if(k==n){
                    output(x[1..n]);
                }else{
                    k=k+1;	// 前进
                    x[k]=0;
                }
            }
        }
        k=k-1;	// 回溯
    }
}
复制代码

解法 4：(求一个解的)迭代

boolean NQueen2(n){
    flag=false;
    k=1;
    x[1]=0;
    while(k>=1 && !flag){
        while(x[k]<n && !flag){
        	x[k]=x[k]+1;
            if(place(k)){
                if(k==n){
                    output(x[1..n]);
                    flag=true;
                }else{
                    k=k+1;	// 前进
                    x[k]=0;
                }
            } //(否则跳过=>剪枝)
        }
        k=k-1;	// 回溯
    }
    return flag;
}
复制代码

5.3 八数码问题

另见博客：blog.csdn.net/u012283461/…

5.4 迷宫问题（迭代：一个解）

// 迷宫边界(M[i]=0✔，M[i]=1❌)
// 设置增量数组dx[1..4]、dy[1..4]
// 方向移动：(dx,dy)
// 标记数组 tag[1..m,1..n]
// tag[x,y]=1,位置(x,y)已搜索过; 反之,未搜索过~
// flag:标记是否存在通路
// (ix,iy)表示入口,(x,y)表示当前位置,(ox,oy)表示出口
// 设置数组k[1..n*m]记录当前搜索路径，k[i]表示在第i个位置的前进方向
/**
 * 状态空间:{(k1,k2,...,ks)|ki∈{1,2,3,4},i=1,2,..,s,1<=s<=m*n}
 * 其中,ki表示搜索方向,方向编号为:
 * 1-东、2-南、3-西、4-北
 */
void MAZE(){
    (dx[1],dy[1])=(1,0);
    (dx[2],dy[2])=(0,1);
    (dx[3],dy[3])=(-1,0);
    (dx[4],dy[4])=(0,-1);
    
    flag=false;		// 表示是否存在通路
    tag[1..m,1..n]=0;
    // 设置边界
    M[0,0..n+1]=M[m+1,0..n+1]=1;
    M[0..m+1,0]=M[0..m+1,n+1]=1;
    x=ix;
    y=iy;
    tag[x,y]=1;		// 标记是否已经搜索过~
    // !!!
    i=1;			// 相当于“八皇后问题”的 k！
    k[i]=0;			// k[1]-东、k[2]-南、k[3]-西、k[4]-北!
    while(i>=1 && !flag){
        while(k[i]<4 && !flag){
            k[i]=k[i]+1;	// 试沿着下一个方向搜索(按照-东南西北的顺序)
            x1=x+dx[k[i]];
            y1=y+dx[k[i]];
            // 满足约束条件(可走M[x,y]==0、并且没有走过tag[x,y]==0)
            if(M[x1,y1]==0 && tag[x1,y1]==0){
                if(x1==ox && y1==oy){
                    flag=true;
                }else{
                    // 标记当前位置已搜索过~
                    tag[x,y]=1;
                    // 进入新位置
                    x=x1;
                    y=y1;
                    i=i+1;
                    k[i]=0;		// 呼应~
                }
            }
        }
        // 回溯
        i=i-1;
        x=x-dx[k[i]];
        y=y-dy[k[i]];
    }
    
    if(flag){
        outputRoute(k,i);
    }else{
        output("no solution");
    }
}
复制代码

5.5 图的着色问题（迭代：一个解）

// 状态空间:A={(x1,x2,...,xn)|xi∈{1,2,...,m},i=1,2,...,n},其中xi表示顶点i所着的颜色编号
// 输入：正整数m(颜色数),n(顶点数)和含n个顶点的无向连通图G的邻接矩阵graph
// 输出：图G的m着色问题的一个解x[1..n],若无解,则输出no solution
boolean color(k){
    // 在前k-1个顶点已着色的情况下,判断第k个顶点是否可着颜色x[k],是-true,否-false
    j=1;
    while(j<k){
        // 如果k到j有边(graph[k,j]==1)，且颜色相同(x[k]==x[j])，则不能着色!
        if(graph[k][j]*x[k]==x[j]){
            return false;
        }else{
            j=j+1;
        }
    }
    // k的邻接点没有相同颜色，可以为顶点k着色!
    return true;
}

void m-Coloring(){
    flag=false;	// flag标记问题是否有解
    k=1;
    x[1]=0;
    while(k>=1 && !flag){
        while(x[k]<m && !flag){
            x[k]=x[k]+1;		// 试将第k个顶点着下一种颜色
            // 如果第k个顶点的当前颜色合法(即满足约束条件)~
            if(color(k)){
                if(k==n){
                    flag=true;
                }else{
                    k=k+1;
                    x[k]=0;
                }
            } //否则，剪枝
        }
        k=k-1;
    }
    
    if(flag)
        output x;
    else
        output "no solution!";
}
复制代码

5.6 哈密顿回路（递归：所有解）

哈密顿回路：图 G 的哈密顿回路是一条经过 G 的所有顶点恰好一次的回路。

// 状态空间: A={(x1,x2,...,xn)|x1=1,2<=xi<=n,i=2,..,n},其中,x1,x2,...,xn表示G中的顶点序列
// 解的约束条件: graph[x[k-1],x[k]]=1,k=2,3,...,n 且 graph[x[n],x[1]]=1 且 x[i]!=x[j](i!=j)
// tag[1..n]表示顶点是否在当前生成的路径上:
    tag[i]=1,顶点i在当前路径上;
    tag[i]=0,顶点i不在当前路径上;
// 注意：当一个顶点退出当前路径时，该顶点的标记应该复原为0
// 输入：正整数n和含n个顶点的连通图G的邻接矩阵graph
// 输出：图G的所有哈密顿回路
void main(){
    // 用x[1..n]表示搜索路径,从顶点1开始,x[i]表示当前路径上的第i个顶点~
    x[1]=1;
    x[2..n]=0;
    // 设顶点标记初值
    tag[1]=1;
    for(i=2 to n){
        tag[i]=0;
    }
    // 1作为初始点
    hamilton(2);
}


boolean route(k){
    // 判断当前顶点x[k]是否可作为当前路径x[1..k-1]的下一个顶点(k<n时，直接短路后边的语句)
    if((graph[x[k-1],x[k]]==1) && (tag[x[k]]==0) && (k<n || (k==n && graph[x[k],1]==1))){
        return true;
    }else{
        return false;
    }
}


void HamilTonian(k){
    for(i=2 to n){
        x[k]=i;			// 当前路径的第k个顶点为图上顶点i
        if(route(k)){
            tag[x[k]]=1;	// 第i顶点已被标记~
            if(k==n){
                output x[1..n];
            }else{
                HamilTonian(k+1);
            }
        	tag[x[k]]=0;	// 回溯回来后，重置tag[x[k]]，以便于重复利用~
        }
    }
}
复制代码

5.7 子集和问题

给定含有

n

个正数的集合

S=\{a_1,a_2,...,a_n\}

b

，求

S

的元素之和等于

b

的子集。

void subset(k){
    sum=∑ai·xi;	// 从i=1 to k
    r=∑ai;		// 从i=k+1 to n
    // 在已经求出的部分解x[1..k]固定的情况下，求关于S，b的子集和问题的所有解并输出，有解返回true，否则false
    if(sum==b){
        x[k+1,..,n]=0;
        output(x[1..n]);
    	t=true;
    }else{
        if(k<n && sum<b && sum+r>=b){
            x[k+1]=0;
            t1=subset(k+1);		// 搜索左子树
            x[k+1]=1;
            t2=subset(k+1);		// 搜索右子树
            t=t1||t2;	// 存在一个解即为true
        }else{
            t=false;
        }
    }
    return t;
}
复制代码

5.8 0/1 背包问题

剪枝条件：设当前部分解为

(x_1,x_2,...,x_k)

maxv

，则当前背包剩余容量为

r=C-\sum_{i=1}^{k}s_ix_i

cv=\sum_{i=1}^{k}v_ix_i

（1）

r<=0

（2）

\sum_{i=k+1}^{n}s_i\leq r

cv+\sum_{i=k+1}^{n}v_i

（3）

cv+\sum_{i=k+1}^{n}v_i\leq maxv

输入：物品数

n

，

n

种物品的体积数组

s[1..n]

和价值数组

v[1..n]

，背包容量

C

输出：装入背包物品的最大总价值

maxv

和最优解

x_0[1..n]

void main(){
    rv=0;	rs=0;
    // 初始化rv、rs
    for(i=1 to n){
        rv=rv+v[i];
        rs=rs+s[i];
    }
    maxv=0;
    x0[1..n]=x[1..n]=0;
    knapsack(0,C,0,rv,rs);
    output maxv,x0[1..n];
}

void knapsack(k,r,cv,rv,rs){
    // 找到更优的解，更新当前最优值
    if(r>=0 && cv>maxv){
        maxv=cv;
        x0[1..k]=x[1..k];
        x0[k+1..n]=0;
    }
    
    if(rs<=r){		// 对应剪枝条件（2）
        // 如果剩余的背包容量足够装剩余未装入的所有物品，且全部装入后大于当前最优值时
        if(cv+rv>maxv){
            // 更新
            maxv=cv+rv;
            x0[1..k]=x[1..k];
            x0[k+1..n]=1;
        }
    }else{
        if(r>0 && cv+rv>maxv){
            rv=rv-v[k+1];
            rs=rs-v[k+1];
            // 不装入第k+1件物品
            x[k+1]=0;
            knapsack(k+1,r,cv,rv,rs);	// 搜索左子树
            x[k+1]=1;
            knapsack(k+1,r-s[k+1],cv+v[k+1],rv,rs);		// 搜索右子树
        }
    }
}
复制代码

6. 算法设计 🏆

6.1 求第二小元素

使用分治算法，在一个含 n 个元素的数组中找出第 2 小元素

public void main(){
    // 获取最小和次小的元素
	(x,y)=min_12(1,n);
    // 输出第2小元素
    output y;
}

/*
 * 求A[low..high]中的最小元素和第二小元素(x,y)并返回
 */
private int[] min_12(low,high){
    
    if(low == high){
        // 相当于只返回一个数
        return (A[low],MAX_INT);
    }else{
        if(low + 1 == high){
            if(A[low]<A[high])
                return (A[low],A[high]);
            else
                return (A[high],A[low]);
        }else{
            // 伪代码中: ⌊(low+high)/2⌋;
            // 高级程序语言中: (low+high)/2;
            mid = ⌊(low+high)/2⌋;
            (x1,y1) = min_12(low,mid);
            (x2,y2) = min_12(mid+1,high);
            
            if(x1 < x2){
                return (x1, min{y1,x2});
            }else{
                return (x2, min{y2,x1});
            }
            
        }
    }
}
复制代码

6.2 格雷码算法

graycode(arr,m,n)
	if(m==n)
        output arr[1..n];
    else
        graycode(arr,m+1,n);
        arr[m]=arr[m].equals["0"] ? "1" : "0";
        graycode(arr,m+1,n);
	end if
end graycode
复制代码

6.3 金钱兑换算法

未完待续...

6.4 旅行者加油算法

未完待续...

6.5 骑士周游算法

未完待续...

6.6 马走日字算法

m

行

n

列棋盘的

S

点处有一中国象棋马，给出棋盘上的另一点

T

，设

T

在

S

的右边。

规定马走日字且只能向右走，要从

S

走到

T

，马至少要走多少步？

（1）该问题的最优子结构是什么？

（2）请写出递归关系式

（3）写出求解该问题的最优值的动态规划算法

$未完待续...$

希望本文对你有所帮助🧠
欢迎在评论区留下你的看法🌊，我们一起讨论与分享🔥

1. 归纳🍺

1.1 选择排序

1.2 插入排序

1.3 整数幂问题

组合求解

1.4 棋子移动游戏

1.5 多项式求值

1.6 寻找多数元素

归纳法求解

1.7 生成全排列

2. 分治法🐱‍👤

2.0 快速排序

2.1 归并排序

2.2 大整数乘法

解法 1：分治法

解法 2：算法改进

2.3 矩阵乘法

解法 1：简单递归法

解法 2：STRASSEN 算法

2.4 寻找第 k 小元素

随机化的线性选择算法

2.5 最近点对问题

分治法

3. 动态规划🐙

引例：Fibonacci

解法 1：迭代算法

解法 2：基于记忆的递归（动态规划）

3.1 矩阵链乘问题（填表）

3.1.1(1) 解法 1：自顶向下的递归算法（求解最优值）

3.1.1(2) 解法 2：自底向上的迭代算法（求解最优值）

3.1.2 最优乘法顺序（构造最优解）

3.2 最长公共子序列问题（填表）

3.2.1 LCS 迭代算法：求解最长公共子序列的长度（求解最优值）

3.2.2 LCSS 迭代算法：构造最长公共子序列（构造最优解）

3.3 嵌套矩形问题

3.3.1 求解最优值

3.3.2 构造最优解

3.4 0/1 背包问题（填表）

3.4.1 求解最优值

3.4.2 构造最优解

4. 贪心算法🔥

4.1 Prim 算法

4.2 Huffman 算法

4.3 有期限的作业安排问题

4.4 分数背包问题

4.5 多机调度问题

4.6 活动安排问题

5. 回溯法🌊

5.0 回溯算法模板

5.0.1 求所有解的递归算法

5.0.2 求一个解的递归算法

5.0.3 求所有解的迭代算法

5.0.4 求一个解的迭代算法

5.1 子集生成

解法 1：增量构造法

解法 2：位向量法

5.2 八皇后问题

解法 0：(求所有解的)枚举法（递归）

解法 1：(求所有解的)枚举法 + "剪枝"（递归）

解法 2：(求一个解的)递归

解法 3：(求所有解的)迭代

解法 4：(求一个解的)迭代

5.3 八数码问题

5.4 迷宫问题（迭代：一个解）

5.5 图的着色问题（迭代：一个解）

5.6 哈密顿回路（递归：所有解）

5.7 子集和问题

5.8 0/1 背包问题

6. 算法设计 🏆

6.1 求第二小元素

6.2 格雷码算法

6.3 金钱兑换算法

6.4 旅行者加油算法

6.5 骑士周游算法

6.6 马走日字算法

近期文章

近期评论

标签

热门

文章归档