Algorithm Code randomization

This article records my learning process of the course “Algorithm Design and Analysis” in this semester

1. Induction 🍺

1.1 Selection Sort

O(n2)O(n^2)O(n2)

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

private static void selectSort(s,t,A){ // Select sort A[s..t] in ascending order
    if(s<t){
        k=s;
        for(j=s+1 to t){	// Select the smallest element in A[s..t]
            if(A[j]<A[k])
            k=j;
        }
        if(k! =s) A[s]<->A[k];// switch A[s], A[k]
        selectSort(s+1,t,A);// Select sort A[s+1..t] in ascending order}}Copy the code

1.2 Insertion Sort

O(n2)O(n^2)O(n2)

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

private static void insertSort(s,t,A){ // Insert sort A[s..t] in ascending order
    if(s==t){
        return;        
    }else{
        insertSort(s,t-1,A);	// Insert sort A[s...t-1] in ascending order
        x=A[t];
        j=t-1;
        while(j>0&&A[j]>x){
            A[j+1]=A[j];
            j=j-1;            
        }
        A[j+1]=x; }}Copy the code

1.3 Integer power problem

Combination to solve

⋅ Logn O(N · Logn)O(N ⋅ Logn)

public static void main(a){
    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;
        returny; }}Copy the code

1.4 Pawn movement game

Time complexity: O(n)O(n)O(n)

public static void main(a){
    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{
        // The first group of actions
        move(n,2n+1);
        move(n+1,2n+2);
        // Second set of actions
        move(2n-1,n);
        move(2n,n+1);
        chessMove(n-1);	// Recursively solve the n-1 subproblem}}Copy the code

1.5 Polynomial evaluation

Pn(x)= ANXn +an−1xn−1+… + a1x, a0 (array length is n + 1) P_n (x) = a_nx ^ n + a_ {}, n – 1 x ^ {}, n – 1 +… + a_1x + a_0 (array length: \ n+1) Pn(x)= ANXn +an−1xn−1+… +a1x+a0 (array length n+1)

Time complexity: O(n)O(n)O(n)

public static void main(a){
    // Note that the initial value of n is 0
    horner(A,0,x);
}

private static int horner(A, n, x) {
    // the value of a.length is n+1
    if (n == A.length - 1) {
        return A[n];
    } else {
        return x * horner(A, n + 1, x) + A[n]; }}Copy the code

1.6 Finding most elements

It’s solved by induction

Time complexity: O(n)O(n)O(n)

public static void main(a){
    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;
}

/** * array of n elements: 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);
}
Copy the code

1.7 Generate full permutation

C: O(N ⋅ N!) O (n, n!) O (n ⋅ n!)

Note: Do not store full permutations; Elements need to be swapped back to stay in their original state!

public static void main(a){
    // P[1...n] holds each permutation
    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]);	// The output is not stored, but immediately changed back to the original state
            // P[m...n] = m, m+1... , n}}}Copy the code

2. Divide and conquer 🐱👤

2.0 Quicksort

⋅ Logn O(N · Logn)O(N ⋅ Logn)

Space complexity: O(1)O(1)O(1)

void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); // Swap the middle number with the first number
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // Find the first number less than x from right to left
                j--;  
            if(i < j) 
                s[i++] = s[j];
            
            while(i < j && s[i] < x) // Find the first number greater than or equal to x from left to right
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        / / partition
        s[i] = x;
        quick_sort(s, l, i - 1); 	// recursive call
        quick_sort(s, i + 1, r); }}Copy the code

2.1 Merge Sort

Input: array of n elements A[1…n]A[1…n]A[1…n]

⋅ Logn O(N · Logn)O(N ⋅ Logn)

Space complexity: O(n)O(n)O(n)

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

private static void mergeSort(A, low, high){
    // merge A[low...high] in non-descending order
    if(low < high){
        mid = (low+high)/2;			/ / decomposition ~
        mergeSort(A, low, mid);		/ / left recursion
        mergeSort(A, mid+1, high);	/ / right recursion
        merge(A, low, mid, high);	~ / / merger}}private static void merge(A, low, mid, high){
    // merge A[mid] and A[mid+1...hi]
    int i = low, j = mid + 1;

    for (int k = low; k <= high; k++)
        // aux[]: auxiliary array required for merging
        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++];
        elseA[k] = aux[i++]; }}Copy the code

2.2 Large integer multiplication

Solution 1: Divide and conquer

Using the divide-and-conquer algorithm, the upper bound can be significantly reduced. For simplicity, assume that n is a power of 2, and the algorithm idea is as follows:

If each integer is divided into two parts and each part is divided into n/2 bits, u and V can be rewritten as u=w2n2+xu =w2 ^\frac{n}{2} +xu =w22n+x and V =y2n2+zv =y2 ^\frac{n}{2} +zv =y22n+z

U =w2n2+xu =w2 ^\frac{n}{2} +xu =w2n +x:

W (high)	X (low level)

V =y2n2+zv =y2 ^\frac{n}{2} +zv =y2n +z:

Y (high)	Z (low)

The product of u and v can be calculated as:
$uv = (w2^\frac{n}{2} + x)(y2^\frac{n}{2} + z) = wy2^n + (wz + xy) 2^n/2 + xz$

The time complexity of the divide-and-conquer algorithm T(n)T(n)T(n) satisfies:

Time complexity: T(n)=O(n2)T(n) =O(n ^2)T(n)=O(n2)

Solution 2: Algorithm improvement

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

Thus, the final expression is:

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

In this way, the multiplication of u and V is reduced to three multiplications of n/2 integers and six addition and subtraction operations, which are θ (n) θ (n) θ (n); This method produces the following recursion:

Time complexity: T (n) = O (nlog23) material (n1.59) T O (n) = O (n ^ {log_2 {3}}) \ approx O (n ^ {} 1.59) T (n) = O (nlog23) material O (n1.59)

2.3 Matrix Multiplication

Problem description: Let A and B be square matrices of order N, and solve C=ABC =ABC =AB

Solution 1: Simple recursive method

Assuming n=2kn =2 ^kn=2k, A, B, and C can be divided into four submatrices of n/2∗n/2n/2 * n/2n/2∗n/2:

Use the divide-and-conquer method to calculate the composition of C, as defined by the following equation:

C=ABC =ABC =AB requires 8 n/2n/2n/2 square matrix multiplication and 4 n/2n/2n/2 square matrix addition.

Let AAA and MMM represent the time of a number addition and multiplication respectively, then the recursive formula of the algorithm is:

Time complexity: T(n)=O(n3)T(n)=O(n^3)T(n)=O(n3)

It can be seen that the divide-and-conquer algorithm does not produce effective algorithms. On the contrary, it consumes more time than the traditional method. The increased time and space cost comes from the management overhead brought by recursion. In other words, this is just a recursive form of the traditional method, and the only difference between the two algorithms is the order in which the matrix elements are multiplied.

Solution 2: STRASSEN algorithm

Time complexity: O (nlog7) material (n2.81) O O (n ^ {log7}) \ approx O (n ^ {} 2.81) O (nlog7) material O (n2.81)

2.4 Find the KTH element

Time complexity: O(n)O(n)O(n)

Stochastic linear selection algorithm

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

select(A,low,high,k){
    // Find the KTH element in A[low..high] and return it
    p=high-low+1;	// p is the number of elements being processed
    if(p<44) {// If the number of elements is less than 44
        // tell A[low..high] sort
        sort(A[low..high]);
    	return (A[low+k-1]);
    }
    // The following subproblem is decomposedQ = ⌊ p /5⌋;
    // Divide A[low..low+5q-1] into q groups with 5 elements in each group, sort each group separately and find the middle items, all the middle items are stored in array M[1..q]
    mm=select(M,1, ⌈ q/q2⌉);		// Find the middle term of M
    // Divide A[low..high] into three groups
    A1={a|a<mm};
    A2={a|a=mm};
    A3={a|a>mm};
    // Select one of the following subproblems to recurse or solve directly
    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|); }}Copy the code

2.5 Recent point-to-point problems

Algorithm idea: divide S into two disjoint subsets, find the nearest point pairs of each subset, and the nearest point pairs of all point pairs in the two subsets respectively, and finally get the nearest point pairs in S by comparison

Time complexity: T(n)=O(nlogn)T(n)=O(nlogn)T(n)=O(nlogn)

Divide and conquer method

I bet you don't have any bullets in your gun
Copy the code

3. Dynamic planning 🐙

Quotes: Fibonacci

Solution 1: Iterative algorithm

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
Copy the code

Solution 2: Memory-based recursion (dynamic programming)

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
Copy the code

3.1 Matrix chain Multiplication problem (fill in the form)

Time complexity: O(n3)O(n^3)O(n3)

Space complexity: O(n2)O(n^2)O(n2)

3.1.1(1) Solution 1: Top-down recursive algorithm (to solve the optimal value)

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

// initial c[][]=-1, and the row and column value of the ith matrix is r[I], r[I +1]
private static int MM(r[],j,k){
    if(j==k)		// There is only one matrix ~
        return 0;
    else if(c[j,k]! = -1)		// This value exists (the subproblem has been marked) and can be returned directly! (Improve efficiency)
        return c[j,k];
    
    minV = MAX_INT;
    for(int i=j+1; j<=k; j++){	// Enumerate parenthesized positions
        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];
}
Copy the code

3.1.1(2) Solution 2: Bottom-up iterative algorithm (solving the optimal value)

public static void main(a){
    // Input: the number of matrices n, order r[1..n+1], where r[k], r[k+1] are the row and column values of the KTH matrix respectively
    [1..n, 1..n] [1..n, 1..n]
    Matchain();
}

private static. Matchain(){for(int i=1; i<=n; i++)
        C[i,i]=0;		// Set the diagonal to 0
    for(d=1 to n-1) {D (1) to d(n-1)
        for(i=1 to n-d){	// Count n-d elements of diagonal 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;		/ / update the value
                    S[i,j]=k;		// Record the split position}}}}return C[1,n], S;
}
Copy the code

3.1.2 Optimal Multiplication Order (Construct optimal solution)

Input: matrix n,M1,M2… ,Mnn,M_1,M_2,… ,M_nn,M1,M2,… The optimal multiplication, Mn, order information array S [1.. n, 1.. n] S [1.. n, 1.. n] S [1.. n, 1.. n]

Output: matrix chain product calculated in optimal order M=M1M2… MnM=M_1M_2… M_nM=M1M2… Mn

/ / call 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);		// Compute the product of two matrices C=AB
        returnC; }}Copy the code

3.2 Longest Common Subsequence problem (fill in the table)

3.2.1 LCS iterative algorithm: Solving the length of the longest common subsequence (solving the optimal value)

LCS time complexity: θ (nm) θ (nm) θ (nm)

LCS spatial complexity: θ (nm) θ (nm) θ (nm)

Input: n, m, A= a1A2… The an and B = b1b2… BNN, m, A=a_1a_2… A_n, B = b_1b_2… B_nn, m, A=a1a2… The an and B = b1b2… bn

Output: the length of A and B L/n, m L/n, m/n, m and L array of information about storage LCS H [1.. n, 1.. m] H [1.. n, 1.. m] H [1.. n, 1.. m]

private static. LCS(){// Initialize the edge ~
    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; }}}}// Return relevant information (H for LCSS algorithm)
    return L[n,m], H;
}
Copy the code

3.2.2 LCSS iterative algorithm: Construct the longest common subsequence (Construct the optimal solution)

H [I, j) = 0 H [I, j) = 0 H [I, j) = 0, in front of the C insert aia_iai, and forward to the H/I – 1, j – 1 H [] I – 1, j – 1 H [I – 1, j – 1]. (C contains ai)(C contains a_i)(C contains AI)

H/I, j = 1 H/I, j = 1 H I, j = 1, then move on to H/I – 1, j H [j] I – 1, H (I – 1, j). (C does not contain AI)(C does not contain a_i)(C does not contain AI)

H [I, j] [I, j) = = 2 H 2 H, I, j = 2, then move on to H H [I, j – 1]] [I, j – 1 H [I, j – 1]. (C does not include bi)(C does not include B_i)(C does not include bi)

private static int[] LCSS(){
    C=[]; i=n; j=m;
    while(i>0 && j>0) {if(H[i,j]==0){
            C=a[i]+C;	// Append ~ in reverse order
            i=i-1;
            j=j-1;
        }else{
            if(H[i,j]==1){
                i=i-1;
            }else{
                j=j-1; }}}return C;
}
Copy the code

3.3 Nested rectangles

3.3.1 Solving the optimal value

Time complexity: O(n+ E)O(n+e)O(n+e)

Space complexity: O(n2)O(n^2)O(n2)

public static void main(a){
    // d[1..n] saves the maximum path length of each vertex in DAG
    c=BuildGraph();		// construct the adjacency matrix c
    for(i=1 to n)		// initialize d[I]
        d[i]=-1;
    for(i=1 to n)
        d[i]=maxlength(i);
    max=d[1];
    // Find the longest path of DAG ~ from the longest path of each vertex
    for(i=1 to n)
        if(max<d[i])
            max=d[i];
    
    return 1+max;
}

// Calculate the maximum path length of I in DAG
private static int maxlength(i){
    if(d[i]>-1)
        return d[i];	// d[I] has been evaluated
    // if d[I] is not found, find the longest path from the next node
    max=0;
    for(j=1 to n){
        if(c[i,j]>0) {// Vertex j is the successor of vertex I
            x=maxlength(i);		// Find the longest path length of vertex j
            if(max<1+x)
                max=1+x;
        }
    }
    d[i]=max;
    return d[i];
}
Copy the code

3.3.2 Constructing the optimal solution

Input: n rectangles

Output: the maximum number of n rectangles that can be nested

// Array d[1,..,n] holds the maximum path length of each vertex in DAG
Nested_Rectangle_Rec(){
    c=BuildGraph();		// create an adjacency matrix c
    for(i=1 to n)
        d[i]=-1;
    for(i=1 to n)
        // The shortest path length from each point
        d[i]=maxlength(i);
    max=d[1];
    for(i=1 to n){
        if(max<d[i])
            max=d[i];
    }
    return 1+max;
}
Copy the code

3.4 0/1 Backpack Problem (fill in the form)

3.4.1 Solving the optimal value

Time complexity:

• ⋅C: O(N C)O(N ·C)O(N C)
• θ (n) θ (n) θ (n)

⋅C: O(N C)O(N ·C)O(N C)

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

// Initialization of the knapsack problem
private static. KnapsackRec(){for(i=0 to n)
        for(j=0 to C)
            V[i,j]=-1;	// All values are solved by ~
    maxV = knapsack(n,C);
    return maxV, H;
}

/** * solve knapsack problem * Let a knapsack of capacity C, n items U={u1,u2,.. , UN}, item u[j] volume and value are s[j] and v[j] * v[I,j] I represents optional items,j represents capacity, v[I,j] value represents value * the corresponding information of optimal solution is stored in array H[0..n, 0..C] * H[I,j]=1, Means that the item U [I] is loaded into the backpack when solving the subproblem corresponding to V[I,j] ~ * H[I,j]=0, means that the item U [I] is not loaded into the backpack when solving the subproblem corresponding to V[I,j] ~ */
private static void knapsack(i,j){
    // The corresponding subproblem is not solved
    if(V[i,j]==-1) {if(i==0||j==0) {// There is not enough capacity or no items left (to the boundary)
            V[i,j]=0;
        }else if(s[i]>j){
            // U [j], also choose not to put items
            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{
        // The value already exists
        returnV[i,j]; }}Copy the code

3.4.2 Constructing the optimal solution

Using the information array H of the optimal solution, the optimal solution (x1,x2… ,xn)(x_1,x_2,… ,x_n)(x1,x2,… ,xn)

When the H/I, j = 1 H/I, j = 1 H I, j = 1, said solving V [I, j] V [I, j] V [I, j] corresponding subproblem when u [I] the item u u [I] [I] into the bag When H [I, j] [I, j) = 0 H = 0 H [I, j) = 0, Means the item u[I]u[I]u[I]u[I] is not loaded into the backpack when solving the corresponding sub-problem of V[I,j]V[I,j]V[I]

Input: n, C, s [1.. n] s volume [1.. n] ‘s [1.. n], the optimal solution information H [0.. n, 0..] C H [0.. n, 0..] C H [0.. n, 0.. C]

Output: the remaining capacity of the corresponding 0/1 knapsack problem

private static int[] Knapsack_solution(){
    // y indicates the remaining capacity of the backpack ~
    y=C;
    X[n]=H[n,C];
    for(i=n to 2) {// If the mark is loaded, subtract the corresponding item capacity from the backpack
        if(X[i]==1)
            y=y-s[i];
        // Recursively solve the residual optimal solution ~
        X[i-1]=H[i-1,y];
    }
    return X;
}
Copy the code

4. Greedy algorithms 🔥

4.1 Prim algorithm

Prim () {T = ∅; x={1},Y=V-{1};	// start with V1
     
     while(T! From = ∅) {{(u, v) | u ∈ X, v ∈ Y} select the minimum weight of edge (X, Y); X = X ∪ {} y;// Add point y from set X
         Y=Y-{y};	// Delete point Y from set YT = T ∪ {} (x, y);// Add edges (x,y) to the edge set of the minimum spanning tree}}Copy the code

4.2 Huffman algorithm

See also blog: blog.csdn.net/fx677588/ar…

4.3 Scheduling problems with deadlines

See also the blog: blog.csdn.net/qq_45815776…

4.4 Score backpack problem

Time complexity: θ (NLogn) θ (NLogn) θ (NLogn)

Input: real number CCC for backpack capacity, item number NNN, real array s[1..n]s[1..n] S [1..n] and V [1..n]v[1..n]v[1..n] v[1..n]v[1..n]v[1..n] V [1..n] V [1..n] V [1..n]

Output: MaxVMaxvMaxV and the corresponding optimal solution x[1..n]x[1..n]x[1..n]

/** * mathematical model: z = Max {v1x1+v2x2+... + VNXN} * * xi indicates the proportion of item I in the backpack to the whole item (0<=xi<=1) */
Greedy_Knapsack(){
    for(i=1 to n)
        y[i] = v[i]/s[i];	// Find the unit volume value of n items
    
    / / to [1.. n] y sorted in descending order address, sort the results returned to the array d [1.. n], make y [1] [d] > = y [2] [d] > =... >=y[d[n]]
	d=sort(y,n);
    for(i=1 to n)
        x[i]=0;		// Initialize x[1..n]
    i=1; maxv=0; rc=C;	// The following rc represents the remaining capacity of the current backpack
     
    while(rc>0 && i<=n){
        j=d[i];		// u[j] select item for current consideration
        if(s[j]<=rc){
            // select item u[j]
            x[j]=1;
        	rc=rc-s[j];
        }else{
            // Select part of item u[j] to fill the backpack
            x[j]=rc/s[j];
            rc=0;
        }
        maxv=maxv+v[j]*x[j];
        i=i+1;
    }
    
    return maxv,x[1..n];
}
Copy the code

4.5 Multiple Machine Scheduling Problems

Time complexity: Θ (Max {nlogn, nm}) Θ (Max \ {nlogn, nm \}) Θ (Max {nlogn, nm})

Input: job number NNN, machine number MMM, integer array t[1..n]t[1..n]t[1..n] t[1..n]t[1..n] f[1..m]f[1..m]f[1..m] f[1..m]

Output: Approximate minimum time required to process NNN jobs on MMM machine mintmintmint

MMJA(){
    f[1..m]=0;
    
    / / on t [1.. n] sorted in descending order address, sort the results returned to the array a [1.. n], makes t [a [1]] [a [2]] > > = t =... >=t[a[n]]
	a=sort(t,n);
    for(i=1 to n){
        j=min(f,m);			// Find the subscript for the minimum of f[1..m]
        f[j]=f[j]+t[a[i]];
    }
    mint = max(f,m);	// Find the maximum value of f[1..m] (i.e., the optimal approximation of multi-machine scheduling, take the maximum value -- barrel principle)
    
    return mint;
}
Copy the code

4.6 Arrangement of activities

Greedy selection strategy: Schedule activities from morning to night according to their end time, and each time choose an activity with the earliest possible end time compatible with the selected activities.

Local optimality: Leave resources as much time as possible at a time to accommodate other activities.

Time complexity: θ (NLogn) θ (NLogn) θ (NLogn)

/** * Number of activities n, which represents the array s[1..n] and f[1..n] */ of n start and end times of activities
Activity_Arrangement()
    
    / / to f [1.. n] sort in ascending order address, sort the results returned to the array d [1.. n], make f [1] [d] [2] [d] < < = f =.. <=f[d[n]]
    d=sort(f,n);
    A={d[1]};
	j=d[1];		// The following j always represents the last activity to end in the current collection A
	for(i=2 to n){
        if(s[d[i]]>=f[j]){
            A=A+{d[j]};		// Add activity d[I] to Aj=d[j]; }}return A;

end Activity_Arrangement
Copy the code

5. Retrospective method 🌊

5.0 Backtracking algorithm template

1. State space (form of solution)
2. The constraint
3. State transition

Let the solution space of the problem be A={(x1,x2… , xn) ∣ xi ∈ xi, I = 1, 2,… ,n}A=\{(x_1,x_2,… , x_n) | x_i ∈ x_i, I = 1, 2,… ,n\}A={(x1,x2,… , xn) ∣ xi ∈ xi, I = 1, 2,… ,n}

• Formal recursive algorithm
• Formal iterative algorithm

5.0.1 Recursive algorithm for all solutions

void advance2(k){
    // In the obtained partial solutions (x1,x2... ,xk-1) is fixed, all the solutions of the problem are solved and output
    for(i=1 to n_k){		// n_k is the number of elements X_kX [k]= the ith element of the set Xk;if((x1,x2,... ,x_k) satisfies the constraint condition of the solution){if(k==n){
                output(x[1..n]);
            }else{
                advance2(k+1); }}}}Copy the code

5.0.2 Recursive algorithm for finding a solution

boolean advance1(k){
    // In the obtained partial solutions (x1,x2... ,xk-1) is fixed, and a solution of the problem can be found
    for(i=1 to n_k){		// n_k is the number of elements X_kX [k]= the ith element of the set Xk;if((x1,x2,... ,x_k) satisfies the constraint condition of the solution){if(k==n){
                output(x[1..n]);
                return true;
            }else{
                t=dvance1(k+1);
                if(t)	return true; }}}return false;
}
Copy the code

5.0.3 Iterative algorithm for all solutions

void BackTrackiter2(a){
    k=1; X1 = the preceding element of the first element in the set x1;while(k>=1) {while{x[k]= the next element in the set Xk;if(satisfy constraint){if(k==n){
                    output(x[1..n]);
                }else{
                    k=k+1;	/ / to go forwardX [k]= the preceding element of the first element in the set Xk; }}// Otherwise, prune
        }
        k=k-1;	/ / back}}Copy the code

5.0.4 Iterative algorithm for finding a solution

void BackTrackiter2(a){
    flag=false;
    k=1; X1 = the preceding element of the first element in the set x1;while(k>=1 && !flag){
        whileXk sets are not exhausted. Flag){x[k]= the next element in the Xk set;if(satisfy constraint){if(k==n){
                    output(x[1..n]);
                    flag=true;
                }else{
                    k=k+1;	/ / to go forwardX [k]= the preceding element of the first element in the set Xk; }}// Otherwise, prune
        }
        k=k-1;	/ / back}}Copy the code

5.1 Subset Generation

Solution 1: incremental construction

Call subset1(1)

void subset1(k){
    for(i=1 to k)
        output(A[k]);	// Prints the current collection
    // Do special processing on the root of the entire tree
    if(k==1)
        s=1;
    else
        s=A[k-1] +1;	// Determine the lowest possible value for the current node to expand down
    for(i=s to n){
        A[k]=i;
        subset1(k+1);	// Construct subsets recursively}}Copy the code

Solution 2: bitvector method

void subset2(k){
    if(k==n+1) {// B[1..n] is already assigned
        for(i=1 to k){
            if(B[i]) output[i];
        }
    }
    B[k]=1;	// select the KTH element
    subset2(k+1);
    B[k]=0;	// do not select the KTH element
    subset2(k+1);
}
Copy the code

5.2 The Eight Queens Problem

place.java

boolean place(k){
    // Determine if the queen on line K conflicts with the queen on line 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;
}
Copy the code

Solution 0: enumeration of all solutions (recursion)

/ / call: nqueenBruteForce (1);

void nqueenBruteForce(k){
    // In the case that k-1 queens have been placed in the previous k-1 row
    for(i=1 to n){
        x[k]=i;	// Try to place the queen in row k in column I
        
        if(k==n){	// Find a permutation of n queens
            if(place()){
                // If there is no conflict, output
                output(x[1..n]); }}else{
            // x[1..k] is just a partial arrangement of queens
            t1=nqueenBruteForce(k+1);	// Recursively, continue to arrange queens from line k+1}}}Copy the code

Solution 1: enumeration of all solutions + “prune” (recursive)

void nqueen2(k){
    // In the case that k-1 queens have been placed in the previous k-1 row
    for(i=1 to n){
        // Try to place the queen in row k in column I
        x[k]=i;
        // Line k is placed immediately to determine whether the conflict (conflict, pruning)
        if(place(k)){
            if(k==n){
                // If there is no conflict, output
                output(x[1..n]);
            }else{
            	nqueen2(k+1); }}}}Copy the code

Solution 2: recursion of a solution

boolean nqueen3(k){
    // In the case that k-1 queens have been placed in the previous k-1 row
    for(i=1 to n){
        // Try to place the queen in row k in column I
        x[k]=i;
        // Line k is placed immediately to determine whether the conflict (conflict, pruning)
        if(place(k)){
            if(k==n){
                output(x[1..n]);
                // Return when a solution output is found
                return true;
            }else{
                boolean t = nqueen3(k+1);
                if(t) return true; }}}/ / there is no solution
    return false;
}
Copy the code

Solution 3: iterate over all solutions

void NQueen1(n){
    k=1;
    x[1] =0;
    while(k>=1) {while(x[k]<n){
            x[k]=x[k]+1;
            if(place(k)){	// Can also be used to prune
                if(k==n){
                    output(x[1..n]);
                }else{
                    k=k+1;	/ / to go forward
                    x[k]=0;
                }
            }
        }
        k=k-1;	/ / back}}Copy the code

Solution 4: iteration of a solution

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;	/ / to go forward
                    x[k]=0; }}//(otherwise skip => prune)
        }
        k=k-1;	/ / back
    }
    return flag;
}
Copy the code

5.3 Eight digital problems

See also blog: blog.csdn.net/u012283461/…

5.4 Labyrinth Problem (Iteration: One solution)

➤ (M[I]=0✔ T, M[I]=1❌)
Dx [1..4], dy[1..4]
// direction shift :(dx,dy)
// Tag array tag[1..m,1..n]
// tag[x,y]=1; Otherwise, ~ is not searched
// flag: indicates whether a path exists
// (ix,iy) indicates the entry,(x,y) indicates the current position, and (ox,oy) indicates the exit
// Set the array k[1..n*m] to record the current search path, k[I] represents the forward direction at the ith position
/** * state space :{(k1,k2... , ks) | ki ∈ {1, 2, 3, 4}, I = 1, 2,... , s, 1 < = s < = m * n} *, ki said search direction, the direction of Numbers for: * 1-3-2 - south, east, west, north 4 - * /
void MAZE(a){
    (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;		// Indicates whether a path exists
    tag[1..m,1..n]=0;
    // Set boundaries
    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;		// Flag whether ~ has already been searched
    / /!!!!!!
    i=1;			// The equivalent of the eight Queens problem.
    k[i]=0;			// k[1]- east, k[2]- south, k[3]- west, k[4]- north!
    while(i>=1 && !flag){
        while(k[i]<4 && !flag){
            k[i]=k[i]+1;	// Try searching in the next direction (in the order of -southeast, northwest)
            x1=x+dx[k[i]];
            y1=y+dx[k[i]];
            [x,y]==0, without tag[x,y]==0
            if(M[x1,y1]==0 && tag[x1,y1]==0) {if(x1==ox && y1==oy){
                    flag=true;
                }else{
                    // marks that the current location has been searched for ~
                    tag[x,y]=1;
                    // Enter the new position
                    x=x1;
                    y=y1;
                    i=i+1;
                    k[i]=0;		/ / echo ~}}}/ / back
        i=i-1;
        x=x-dx[k[i]];
        y=y-dy[k[i]];
    }
    
    if(flag){
        outputRoute(k,i);
    }else{
        output("no solution"); }}Copy the code

5.5 Graph coloring problem (Iteration: one solution)

State space :A={(x1,x2... , xn) | xi ∈ {1, 2,... , m}, I = 1, 2,... ,n}, where xi represents the color number of vertex I
// Input: positive integer m(number of colors),n(number of vertices) and adjacency matrix graph of the undirected connected graph G with n vertices
// Output: a solution x[1..n] to the m coloring problem of graph G, if no solution, output no solution
boolean color(k){
    // If x[k] is colorable on vertex k, then x[k] is colorable on vertex K
    j=1;
    while(j<k){
        / / if there is a side k to j (graph [k, j] = = 1), and the same color (x = = [k] x [j]), is not color!
        if(graph[k][j]*x[k]==x[j]){
            return false;
        }else{
            j=j+1; }}// Vertex k can be colored!
    return true;
}

void m-Coloring(){
    flag=false;	// flag Indicates whether the problem has a solution
    k=1;
    x[1] =0;
    while(k>=1 && !flag){
        while(x[k]<m && ! flag){ x[k]=x[k]+1;		// Try the KTH vertex with the next color
            // If the current color of the KTH vertex is legal (i.e. satisfies the constraint)~
            if(color(k)){
                if(k==n){
                    flag=true;
                }else{
                    k=k+1;
                    x[k]=0; }}// Otherwise, prune
        }
        k=k-1;
    }
    
    if(flag)
        output x;
    else
        output "no solution!";
}
Copy the code

5.6 Hamiltonian loop (Recursion: All solutions)

Hamiltonian loop: The Hamiltonian loop of a graph G is a loop that passes through all vertices of G exactly once.

State space: A={(x1,x2... , xn) | x1 = 1, 2 < = xi < = n, I = 2,... , n}, among them, the x1, x2,... ,xn represents the sequence of vertices in G
Graph [x[k-1],x[k]]=1,k=2,3,... Graph [x[n],x[1]]=1 and x[I]! =x[j](i! =j)
// tag[1..n] indicates whether the vertex is on the currently generated path:
    tag[i]=1, vertex I is on the current path; tag[i]=0, vertex I is not on the current path;// Note: when a vertex exits the current path, the vertex's marker should revert to 0
// Input: positive integer n and the adjacency matrix graph of the connected graph G with n vertices
// Output: all Hamiltonian loops in figure G
void main(a){
    // use x[1..n] to represent the search path, starting with vertex 1, where x[I] represents the ith vertex ~ on the current path
    x[1] =1;
    x[2..n]=0;
    // set vertex initial values
    tag[1] =1;
    for(i=2 to n){
        tag[i]=0;
    }
    // 1 as the initial point
    hamilton(2);
}


boolean route(k){
    // Check whether x[k] can be the next vertex of x[1..k-1].
    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;			// The KTH vertex of the current path is vertex I on the graph
        if(route(k)){
            tag[x[k]]=1;	// Vertex I is marked ~
            if(k==n){
                output x[1..n];
            }else{
                HamilTonian(k+1);
            }
        	tag[x[k]]=0;	// After backtracking, reset the tag[x[k]] for reuse}}}Copy the code

5.7 Subset sum problems

Given a set of NNN positive numbers S={a1,a2… ,an}S=\{a_1,a_2,… ,a_n\}S={a1,a2,… ,an} and a positive number BBB, find that the sum of the elements of SSS is equal to a subset of BBB.

void subset(k){sum = ∑ ai DE xi;// from I =1 to kR = ∑ ai;// from I =k+1 to n
    // If the partial solution x[1..k] is fixed, find all the solutions for the subset of S, b and the problem and print it, return true if there are solutions, false otherwise
    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);		// Search the left subtree
            x[k+1] =1;
            t2=subset(k+1);		// Search the right subtree
            t=t1||t2;	// There exists a solution that is true
        }else{
            t=false; }}return t;
}
Copy the code

5.8 0/1 Knapsack problem

Pruning condition: Suppose the current partial solution is (x1,x2… ,xk)(x_1,x_2,… ,x_k)(x1,x2,… ,xk), the current optimal value is maxvmaxvmaxV, then the current backpack remaining capacity is r=C−∑ I =1ksixir=C-\sum_{I =1}^{k}s_ix_ir=C−∑ I =1ksixi, The total value of items in the backpack is CV =∑ I = 1kvixICV =\ Sum_ {I =1}^{k} v_IX_ICV =∑ I =1kvixi.

(1) r<=0r<=0r<=0 (backpack is full)

(2) ∑ I =k+ 1Nsi ≤r\sum_{I =k+1}^{n}s_i\leq r∑ I =k+ 1Nsi ≤r\sum_{I =k+1}^{n}s_i\leq r Can get the maximum value of the subtree search to CV + ∑ I = k + 1 nvicv + \ sum_ {I = k + 1} ^ {n} v_icv + ∑ I = k + 1 nvi)

(3) CV +∑ I =k+ 1Nvi ≤ maxvCV +\sum_{I =k+1}^{n}v_i\leq maxVCV +∑ I =k+ 1Nvi ≤maxv

---

Input: item number NNN, NNN Volume array s[1..n]s[1..n] S [1..n]s[1..n] and value array V [1..n]v[1..n]v[1..n] V [1..n], backpack capacity CCC

Output: MaxVMaxvMaxV and optimal x0[1..n]x_0[1..n]x0[1..n]

void main(a){
    rv=0;	rs=0;
    // Initialize 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){
    // Find a better solution, update the current optimal value
    if(r>=0 && cv>maxv){
        maxv=cv;
        x0[1..k]=x[1..k];
        x0[k+1..n]=0;
    }
    
    if(rs<=r){		// Corresponding pruning condition (2)
        // If the remaining backpack capacity is enough to hold all the remaining items, and all the items are greater than the current optimal value
        if(cv+rv>maxv){
            / / update
            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];
            // do not load item k+1
            x[k+1] =0;
            knapsack(k+1,r,cv,rv,rs);	// Search the left subtree
            x[k+1] =1;
            knapsack(k+1,r-s[k+1],cv+v[k+1],rv,rs);		// Search the right subtree}}}Copy the code

6. Algorithm design 🏆

6.1 Finding the second minor element

Use the divide-and-conquer algorithm to find the 2nd smallest element in an array of n elements

public void main(a){
    // Get the smallest and subsmallest elements
	(x,y)=min_12(1,n);
    // Prints the second element
    output y;
}

/* * Find the smallest and second-smallest element (x,y) in A[low..high] and return */
private int[] min_12(low,high){
    
    if(low == high){
        // Return only one number
        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{
            // in pseudocode: ⌊(low+high)/2⌋;
            // High level programming language: (low+high)/2;Mid = ⌊ + high (low) /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}); }}}}Copy the code

6.2 Gray code algorithm

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
Copy the code

6.3 Money exchange algorithm

$To be continued…$

6.4 Traveler refueling algorithm

$To be continued…$

6.5 Knight Tour algorithm

$To be continued…$

6.6 Ma Go Sun Algorithm

There is a Chinese chess horse at the SSS point of the board in column NNN of MMM row, giving another point TTT on the board, let TTT be to the right of SSS.

What is the minimum number of steps a horse must take to walk from SSS to TTT?

(1) What is the optimal substructure of the problem?

(2) Please write down the recursive relation

(3) write the dynamic programming algorithm to solve the optimal value of the problem

$To be continued…$

---

We hope this article will help you 🧠 feel free to leave your thoughts in the comments 🌊, we will discuss and share 🔥