Note: Please specify:www.cnblogs.com/ECJTUACM-87…

The basic idea of enumeration method

The basic idea of enumeration method is to enumerate all possible states according to the proposed problem and verify which are needed and which are not using the conditions given by the problem. Can make a proposition true, is its solution.

Enumeration structure: loop + judgment statement.

Condition of enumeration method

Although enumeration is essentially a search strategy, it differs from the backtracking method described below. Because the problem to be solved by enumeration method must satisfy two conditions:

⑴ The number of elements in each state can be predetermined n;

⑵ State elements A1, A2… The possible values of an are a continuous range of values.

Frame structure of enumeration method

Let ai1 — the minimum value of state element AI; Aik — The maximum value of state element AI (1≤ I ≤n), namely a11≤ A1 ≤ A1K, A21 ≤ A2 ≤ a2K, AI1 ≤ AI ≤ AIK… An1 the an ank or less or less

For A1 ← A11 to A1K do for A2 ←a21 to a2K do …………………… For AI ← AI1 to AIk do …………………… For an←an1 to ank do if state (A1,... Ai,... , an) satisfy the test conditions then output the solution of the problem;Copy the code

Advantages and disadvantages of enumeration methods

Advantages of enumeration method:

(1) Because the enumeration algorithm is generally the “literal translation” of real life problems, it is more intuitive and easy to understand;

(2) Because the enumeration algorithm is based on examining a large number of states, or even enumerating all states, it is easy to prove the correctness of the algorithm

Disadvantages of enumeration method:

The efficiency of enumeration algorithm depends on the number of enumeration states and the cost of enumeration of a single state, so the efficiency is low.

Enumeration: Sets enumeration objects, scopes, and constraints directly according to the topic.

Pay attention to the topic carefully, do not omit any conditions

For example,

Example problem 1: weight weighing

[Problem Description] There are 1g, 2G, 3G, 5G, 10g, 20g weights each several (the total weight <=1000), seeking to use these weights can weigh different weight number.

[File input] Enter the weight number of 1G, 2G, 3G, 5G, 10G and 20g.

[File output] Output can weigh the number of different weights.

[Example] 1 1 0 0 0 0

3

【 analysis 】 According to the input weight information, the maximum number of each weight available is determined, and the number of each weight is continuous, can take 0 to the maximum number, so meet the two conditions of enumeration method, can use enumeration method. When enumerating, the weight can be 1g,2g… , any one or more of 20G weights, the enumeration object can be determined as six weights, the range is the number of each weight. When deciding, only need to judge this weight is newly obtained, or the previous one has been obtained, that is, to judge the weight. Since the weight <=1000g, we can open an array of A [1001] to determine the weight.

The C++ code is as follows:

#include <iostream> using namespace std; int A[1001]={0}; int main( ) { int a,b,c,d,e,f,i,sum,num; int arr[7]; Int a w [7] =,1,2,3,5,10,20 {0}; cin>>a>>b>>c>>d>>e>>f; for(arr[1]=0; arr[1]<=a; arr[1]++) for(arr[2]=0; arr[2]<=b; arr[2]++) for(arr[3]=0; arr[3]<=c; arr[3]++) for(arr[4]=0; arr[4]<=d; arr[4]++) for(arr[5]=0; arr[5]<=e; arr[5]++) for(arr[6]=0; arr[6]<=f; arr[6]++) { sum=0; for(i=1; i<=6; i++) { sum+=arr[i]*w[i]; A[sum]=1; } } num=0; for(i=1; i<=1000; i++) { if(A[i]==1) num++; } cout<<num<<endl; return 0; }Copy the code

Example 2: Matchstick equation

【 Question Description 】 Given n match sticks, how many equations of the form “A+B=C” can you form? A, B, and C in the equation are integers made with matchsticks (if the number is non-zero, the highest digit cannot be 0). Use matchsticks to spell the numbers 0-9 as shown below:

Note:

1. The plus sign and the equal sign each need two matchsticks

2. If A≠B, then A+B=C and B+A=C are regarded as different equations (A, B, C≥0).

2. 3. Smart mattress

[Input] Enter an integer n (n≤24).

[Output] Outputs the number of different equations that can be put together.

Problem description: give you n(n<=24) match stick, ask you to spell out “A + B = C” such equation, find the number of solutions.

The number A,B, and C should be 20 matches. We examine the maximum possible value of A and B: 0~9 the number of matches used in the 10 numbers is 6,2,5,5,4,5,6,3,7,6, it is obvious that the number 1 uses at least 2 matches, let B be 1, then A and C can use up to 18 matches, and C>=A, meet the condition of the maximum value of A is 1111. So enumerations A and B range from 0 to 1111.

To speed things up, you can pre-count the number of matchsticks required for all integers from 0 to 2222 in an array.

The code is as follows:

#include <iostream> using namespace std; 6,2,5,5,4,5,6,3,7,6 int a [2223] = {}; ,2,5,5,4,5,6,3,7,6 const int [10] b = {6}; Int need(int n) {int TMP, num; num=0; if(n==0) return 6; while(n>0) { tmp=n%10; num+=b[tmp]; n/=10; } return num; } int main( ) { int n,A,B,C,D,sum; cin>>n; sum=0; for(int i=10; i<2223; A [I]=need(I); for(int i=0; i<=1000; i++) { for(int j=0; j<=1000; j++) { A=a[i]; B=a[j]; C=n-4-A-B; D=a[i+j]; if(D==C) sum++; } } cout<<sum<<endl; system("PAUSE"); return 0; }Copy the code

Optimization of enumeration algorithm

Time complexity of enumeration algorithm: total number of states * time spent on a single state.

(1) Extracting effective information;

(2) Reduce double counting;

(3) Reduce the original problem to smaller problems;

(4) Cut branches according to the nature of the problem;

⑸ Introduce other algorithms

For example,

You are given n(n<=105) integers, followed by m (m<=105) queries. For each of the two integers I and j, ask the sum of all the digits from the ith to the JTH.

Naive algorithm:

#include <iostream>
using namespace std;
int main( )
{
    int sum,n,m,x,y,i,j,a[106];
    cin>>n>>m;
    for(i=1; i<=n; i++)  cin>>a[i];
    for(i=1; i<=m; i++) {
        cin>>x>>y;
        sum=0;
        for(j=x; j<=y; j++)  sum+=a[j];
        cout<<sum<<endl;
    }
    return 0;
}
Copy the code

Optimization algorithm:

First calculate s [I] = s [I – 1) + a [I]

cin>>n; for(i=1; i<=n; i++){cin>>a[i]; s[i]=s[i-1]+a[i]; } for(i=1; i<=m; i++) { cin>>x>>y; cout<<s[y]-s[x-1]<<endl; }Copy the code

Maximum submatrix problem

【 Question Description 】 Given a two-dimensional array (including positive or negative numbers), please find and the largest submatrix. Such as:

Method 1: “literal” enumeration process

for(x1=1; x1<=n; (x1,y1) for(y1=1; y1<=n; y1++) for(x2=1; X2<=n; // enumerate the bottom right corner of the rectangle (X2,y2) for(y2=1; y2<=n; Y2 ++) inspects the sum of elements in the rectangle whose upper left corner is (x1,y1) and lower right corner is (x2,y2);Copy the code

Let map be a numeric matrix; Sum is the sum of the elements in the current rectangle; Best is the optimal solution. The investigation process is as follows:

Sum = 0; for(x=x1; x<=x2; X++)// calculate the sum of elements in the current rectangle for(y=y1; y<=y2; Y++) sum = sum + map [x] [y]; If (sum > best) best = sum; // Adjust the optimal solutionCopy the code

This algorithm is rather crude, and the cost of enumerating states is O(N6).

Method 2: Start by reducing double counting

The previous one-dimensional situation can be extended to two dimensions. When calculating the sum of the elements of the inner rectangle whose upper left corner is (x1,y1) and lower right corner is (x2,y2), we can also initialize and calculate the sum of the elements s[x][y] of the inner rectangle whose upper left corner is (1,1) and lower right corner is (x,y).

for(x1=1; x1<=n; (x1,y1) {for(y1=1; y1<=n; y1++) { cin>>map[i][j]; s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+map[i][j]; }}Copy the code

For the sum of the elements whose state upper left corner is (x1,y1) and lower right corner is (x2,y2), we can change it to:

sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; If (sum > best) best = sum; // Adjust the optimal solutionCopy the code

Due to the use of the calculated results, the time complexity of the whole algorithm is reduced to O(N4).

Method 3: Extract appropriate information

It is easy to observe that the maximum submatrix problem is the promotion of the maximum continuous subsequence and problem, that is, replacing a line with a surface, elevating a one-dimensional problem to a two-dimensional problem. So the way we compute the largest submatrix is by multiplying the number of rows to get the maximum.

But the question remains, how do you store matrices efficiently?

We can think of a one-dimensional sequence in which the array b[I] represents the sum from the first element to the ith element. If we want to find the sum from the ith element to the JTH element, we only need to calculate the value of b[j]-b[i-1]. Therefore, it can be generalized to a two-dimensional matrix, where b[I][j] represents the sum of the first I elements of the JTH column of the matrix, and A [I][j] represents element data, then compressed storage:

for(i=1; i<=n; I++) for (j = 1; j<=n; j++){cin>>a[i][j]; b[i][j]=b[i-1][j]+a[i][j]; }Copy the code

Thus, we can use a triple loop to find all the rectangle values, i.e. enumerating the start row I and the end row J, compressing the subrectangles into a single row, and becoming a one-dimensional maximization field and problem.

T [k] = Max (t/k – 1, 0) b + b [j] [k] – [I – 1] [k].

Time is O(n3).

Core code:

sum=-0x7fffffff; for(i=1; i<=n; I ++) {for(j= I; j<=n; {t[1]=b[j][1]-b[i-1][1]; // initialize column 1 for(k=2; k<=n; K++) / / decisions: which column {t [k] = Max (t/k - 1, 0) b + b [j] [k] - [I - 1] [k]. if(t[k]>sum)sum=t[k]; } } } cout<<sum<<endl;Copy the code