枚举策略的基本思想
- 在问题所有可能解之集合中一一枚举所有可能元素。
- 以问题所给检验条件判断每个元素的状态（符合或不符合检验条件），符合条件的元素构成问题的解集。
枚举策略的条件
- 可判断状态的元素之数目为有限个。
- 可判断状态的元素可构成一序列集。（即，可依据某一要素（如序列下标），对这些元素进行遍历）
这两点条件也使得枚举策略虽然本质上属于搜索策略，但与同属于搜索策略的回溯策略相异。
枚举策略的框架结构
设在问题的搜索空间中有a1, a2, a3, … ,ak共k个变量，对i ∈ [1…k]有ai_min <= ai <= ai_max，则可依照以下方式对这k个变量进行枚举：
for(int a1 = a1_min; a1 <= a1_max; a1++)
for(int a2 = a2_min; a2 <= a2_max; a2++)
for(int a3 = a3_min; a3 <= a3_max; a3++)
...
for(int ak = ak_min; ak <= ak_max; ak++){
STATEMENTS;
}
举例
砝码称重
【问题描述】设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），求用这些砝码能称出不同的重量个数。
【文件输入】输入1g、2g、3g、5g、10g、20g的砝码个数。
【文件输出】输出能称出不同重量的个数。
【样例输入】1 1 0 0 0 0
【样例输出】3
分析
由题意，该题目中只有有限种重量的砝码（符合条件1），且每种砝码的数量最大值都确定，且取值范围是连续的，可由0逐个取到最大值（符合条件2），因此只需对6种砝码逐个从0到数目最大值进行枚举。确定可称出的不同数量时，因题目所涉及数据量不大（砝码的总重最多是1000）可采用类似基数排序的思想，来避免每获得一个重量就要对所有重量遍历查找一次的情况。
代码
#include <stdio.h>
#define LEN 1010
int r[LEN];
int w[6] = {1, 2, 3, 5, 10, 20};
int main(void){
int a, b, c, d, e, f; //6种砝码的个数
int num = 0;
while(scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF){
for(int a0 = 0; a0 <= a; a0++)
for(int a1 = 0; a1 <= b; a1++)
for(int a2 = 0; a2 <= c; a2++)
for(int a3 = 0; a3 <= d; a3++)
for(int a4 = 0; a4 <= e; a4++)
for(int a5 = 0; a5 <= f; a5++)
r[ a0 * w[0] + a1 * w[1] + a2 * w[2] + a3 * w[3] +
a4 * w[4] + a5 * w[5] ] = 1;
for(int i = 0; i < LEN; i++)
if(r[i] == 1)
num++;
printf("%d\n", num - 1); // 减去砝码总重为0的情况
}
return 0;
}
枚举策略的优化
枚举策略的优缺点
枚举策略的优点:
- 代码直观，易于理解
- 算法的正确性易于证明
- 某些时候在算法局部应用该策略效果很好
枚举策略的缺点:
枚举策略的开销直接取决于状态元素之个数及单个状态枚举之开销。
而枚举策略的缺点也直接导致枚举策略的效率通常很低。因为上述两处开销对于枚举策略的总开销影响过大。例如，假设对k个状态元素应用枚举策略，则此处枚举策略的时间复杂度就至少是O(N ^ k)。而如果在判断每一个状态元素是否符合条件时开销都较大（例如，需要遍历某个数组），则即使状态元素较少，也会导致算法总的时间复杂度较高。据此，我们应避免直接“翻译”题意来使用枚举策略的情况，使用时应对枚举策略做出适当优化，可以有效降低算法开销。
优化准则
- 保证每个状态元素均是独立变量。
- 尽量缩小每个状态元素的取值范围。
- 采用合适的搜索顺序来逐步缩小搜索空间。
例：百钱买百鸡问题
【问题描述】有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求用100元买100只鸡,各为多少才合适?
设公鸡，母鸡，小鸡个数分别为\(x\), \(y\), \(z\)，则可列出方程组$3x+5y+\frac{z}{3}=100 x+y+z=100$
据此可初步写出程序对\(x\), \(y\), \(z\)进行枚举：
#include <stdio.h>
int main(void){
for(int x = 0; x <= 100; x++)
for(int y = 0; y <= 100; y++)
for(int z = 0; z <= 100; z += 3)
if(3 * x + 5 * y + z / 3 == 100
&& x + y + z == 100)
printf("%d %d %d\n", x, y, z);
return 0;
}
这个程序的复杂度是O(N ^ 3)。接下来我们可以从两个角度优化程序：
首先，我们需要减少状态变量的个数。通过第二个方程，我们可以得到\(z=100-x-y\)。这说明\(z\)不是独立变量。再将此方程代入第一个方程，可得\(4x+7y=100\)，这说明y也可以用x表示，即此题中只有一个独立变量x。接下来，我们缩小状态元素的取值范围。由方程\(4x+7y=100\)可以看出\(x\)的取值范围是0到25，这远小于上一份代码中的0到100。由此，我们可写出经过优化的程序：
#include <stdio.h>
int main(void){
for(int x = 0; x <= 25; x++){
int y = 100 - 4 * x;
if(y >= 0 && y % 7 == 0){
y /= 7;
int z = 100 - x - y;
printf("%d %d %d\n", x, y, z);
}
}
return 0;
}
此时，程序的复杂度为O(N)。这个程序甚至省去了代入方程组（中的任一个方程）判断的过程，因为经由上述分析已经知道了\(x\), \(y\), \(z\)为整数的判断条件，从而只要\(y\)为整数，就可获得方程组的一组整数解（因\(x\)必为整数，\(z\)由\(x\)和\(y\)唯一确定）。
例：POJ.1006 Biorhythms
Description
Some people believe that there are three cycles in a person’s life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.
Input
You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.
Output
For each test case, print the case number followed by a message indicating the number of days to the next triple peak, in the form:
Case 1: the next triple peak occurs in 1234 days.
Use the plural form ``days’’ even if the answer is 1.
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
问题的大意即是:
人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。
Input
输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。
当p = e = i = d = -1时，输入数据结束。
Output
从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。
我们可以先初步写出未经优化的代码：
#include <stdio.h>
int main(void){
int p = 0, e = 0, i = 0, d = 0;
int kase = 1;
while(scanf("%d %d %d %d", &p, &e, &i, &d) != EOF){
if(p == -1 && e == -1 && i == -1 && d == -1)
break;
for(int x = d + 1; x <= 21252; x++)
if( (x - p) % 23 == 0
&& (x - e) % 28 == 0
&& (x - i) % 33 == 0)
printf("Case %d: the next triple peak occurs in %d days.\n",
kase++, x - d);
}
return 0;
}
这个程序的搜索空间较大（从不大于365到21252），我们应想办法缩小其搜索空间。考虑到题目中有三个条件需要判断，我们可以用类似于百钱买白鸡题的策略，对三个条件逐个判断来缩小搜索空间。
下面给出优化后的代码：
#include <stdio.h>
int main(void){
int p = 0, e = 0, i = 0, d = 0;
int kase = 0;
while(scanf("%d %d %d %d", &p, &e, &i, &d) != EOF){
if(p == -1 && e == -1 && i == -1 && d == -1)
break;
int x = 0;
for(x = d + 1; x <= 21252; x++)
if((x - p) % 23 == 0)
break;
for( ; x <= 21252; x += 23)
if((x - e) % 28 == 0)
break;
for( ; x <= 21252; x += 23 * 28)
if((x - i) % 33 == 0)
break;
printf("Case %d: the next triple peak occurs in %d days.\n",
++kase, x - d);
}
return 0;
}
可以看到调整搜索顺序使得程序的搜索空间显著减小，而程序的效率也显著提升。
CODEVS.1168 火柴棒等式 (2008年NOIP全国联赛提高组)
题目描述 Description
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：
注意：
- 加号与等号各自需要两根火柴棍
- 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
- n根火柴棍必须全部用上
输入描述 Input Description
输入文件共一行，有一个整数n（n<=24）。
输出描述 Output Description
输出文件共一行，表示能拼成的不同等式的数目。
样例输入 Sample Input
样例1：
14样例2：
18
样例输出 Sample Output
样例1： 2
样例2： 9
数据范围及提示 Data Size & Hint
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。【输入输出样例2解释】
9个等式为:0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
我们先来计算状态元素的取值范围。由题意，本题中最多有24根火柴，除去4根作为运算符后，还可有20根火柴用来摆A, B, C。考虑A和B的取值范围：A和B的最小值显然为0。又，当A或B达到最大值时，其应具有最多的数字位数，而0~9所需的火柴棒数目分别为6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 其中数字1所用的火柴棒数目最少。则假设B = 1，此时可用18根火柴用来摆A和C。又由B > 0知C > A，故A < 9，即A最多为8，恰好可摆出1111，由对称性，这也是B可摆出的位数最多的数字，即1111是A和B的最大值。则C的最大值的上界是2222。
又，考虑到每一个火柴棍表达式中数字的火柴棍个数计算开销是O(N)，当输入数据组数很多时会严重影响效率，故可以在读入数据之前预先计算0~2222所需的火柴棍个数。
下面给出代码：
#include <stdio.h>
#define LEN 2223
// 存放从0到2222所需的火柴棍个数
int num[LEN] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
// 计算自然数n所需的火柴棍数目
int matchNum(int n){
int perNum = 0;
if(n == 0)
return 6;
while(n > 0){
perNum += num[n % 10];
n /= 10;
}
return perNum;
}
int main(void){
// 预处理
for(int i = 10; i < LEN; i++)
num[i] = matchNum(i);
int n = 0;
while(scanf("%d", &n) != EOF){
int kase = 0;
for(int i = 0; i <= 1111; i++)
for(int j = 0; j <= 1111; j++){
int a = num[i], b = num[j],
c = n - 4 - a - b, d = num[i + j];
if(c == d)
++kase;
}
printf("%d\n", kase);
}
return 0;
}
数字之和
【题目描述】 给你n(n<=105)个整数，然后要有m(m<=105)个询问。每个询问给出两个整数i和j，问第i个数字到第j个数字所有数字之和。
下面给出未经优化的代码：
#include <stdio.h>
#define LEN 110
int ar[LEN];
int main(void){
int n = 0, m = 0;
scanf("%d %d", &n, &m);
for(int x = 0; x < n; x++)
scanf("%d", &ar[x]);
for(int x = 0; x < m; x++){
int i = 0, j = 0, sum = 0;
scanf("%d %d", &i, &j);
for(int k = i; k <= j; k++)
sum += ar[k - 1];
printf("%d\n", sum);
}
return 0;
}
对于每个询问，计算第i个到第j个数字之和的开销都是O(N)。在询问数目较多时，这一开销十分巨大。为此，我们可以在将n个数字均读入到ar[]中后，对i ∈ [0…n)使ar[i] += ar[i - 1], 这样数组元素ar[i]中存储的就是第1个数到第i + 1个数之和，从而第i个数到第j个数之和就是ar[j - 1] - ar[i - 1]。
优化后的代码如下：
#include <stdio.h>
#define LEN 110
int ar[LEN];
int main(void){
int n = 0, m = 0;
scanf("%d %d", &n, &m);
for(int x = 0; x < n; x++){
scanf("%d", &ar[x]);
ar[x] += ar[x - 1];
}
for(int x = 0; x < m; x++){
int i = 0, j = 0;
scanf("%d %d", &i, &j);
printf("%d\n", ar[j - 1] - ar[i - 1]);
}
return 0;
}
最大子矩阵和问题 *
【问题描述】 给定一个二维正方形矩阵（含正数或负数，规模为n ^ 2, n <= 1000），请从中找出最大的子矩阵之和。例如：
我们先给出最直观的算法：枚举子矩阵左上角的点(x1, y1)和右下角的点(x2, y2)。
#include <stdio.h>
#include <limits.h>
#define NMAX 1010
int matrix[NMAX][NMAX];
int main(void){
int n = 0, maxSum = -INT_MAX;
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%d", &matrix[i][j]);
for(int x1 = 0; x1 < n; x1++)
for(int y1 = 0; y1 < n; y1++)
for(int x2 = 0; x2 < n; x2++)
for(int y2 = 0; y2 < n; y2++){
int sum = 0;
for(int i = x1; i <= x2; i++)
for(int j = y1; j <= y2; j++)
sum += matrix[i][j];
if(sum > maxSum)
maxSum = sum;
}
printf("%d\n", maxSum);
return 0;
}
直观算法的复杂度是O(N ^ 6)。我们可以参照上一题的思路对程序进行优化：令matrix[x][y]为从(0, 0)到(x, y)的和。这样(x1, y1)和(x2, y2)之间的和就是matrix[x2][y2] - matrix[x2][y1] - matrix[x1][y2] + matrix[x1][y1]。
下面给出优化之后的代码：
#include <stdio.h>
#include <limits.h>
#define NMAX 1010
int matrix[NMAX][NMAX];
int main(void){
int n = 0, maxSum = -INT_MAX;
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
scanf("%d", &matrix[i][j]);
matrix[i][j] = matrix[i][j] + matrix[i - 1][j]
+ matrix[i][j - 1]
- matrix[i - 1][j - 1];
}
for(int x1 = 0; x1 < n; x1++)
for(int y1 = 0; y1 < n; y1++)
for(int x2 = 0; x2 < n; x2++)
for(int y2 = 0; y2 < n; y2++){
int sum = matrix[x2][y2] - matrix[x2][y1]
- matrix[x1][y2] + matrix[x1][y1];
if(sum > maxSum)
maxSum = sum;
}
printf("%d\n", maxSum);
return 0;
}
优化之后的算法复杂度降到了O(N ^ 4)。但我们还想再进一步优化。由刚刚的经验，最大子矩阵和问题是最大子序列和问题的一个扩展，因此我们可以用解决最大子序列和问题的方法来解决最大子矩阵和问题。
同时，我们观察到这样的事实：最大子矩阵和问题计算的是一列列的数累加获得的最大值。这就给了我们存储矩阵的另一个思路: $$\begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1k}\\ a_{11} + a_{21} & a_{12} + a_{22} & a_{13} + a_{23} & \cdots & a_{1k} + a_{2k}\\ a_{11} + a_{21} + a_{31} & a_{12} + a_{22} + a_{32} & a_{13} + a_{23} + a_{33} & \cdots & a_{1k} + a_{2k} + a_{3k}\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ a_{11} + a_{21} + a_{31} + \cdots + a_{k1} & a_{12} + a_{22} + a_{32} + \cdots +a_{k2} & a_{13} + a_{23} + a_{33} + \cdots + a_{k3} & \cdots & a_{1k} + a_{2k} + a_{3k} + \cdots + a_{kk} \end{bmatrix}$$ 这样在计算子矩阵和时就只需要枚举子矩阵的起始行和结束行，两行之间的部分可视作一个一维的最大子序列和问题，只需枚举列数，从而将算法优化到O(N ^ 3)。
下面给出最终优化后的代码：
#include <stdio.h>
#include <limits.h>
#define NMAX 1010
int matrix[NMAX][NMAX];
int max(int a, int b){
return a > b ? a : b;
}
int main(void){
int n = 0, maxSum = -INT_MAX;
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
scanf("%d", &matrix[i][j]);
matrix[i][j] += matrix[i - 1][j];
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
int sum = 0;
for(int k = 0; k < n; k++){
sum = max(sum, 0) + matrix[j][k] - matrix[i - 1][k];
if(sum > maxSum)
maxSum = sum;
}
}
printf("%d\n", maxSum);
return 0;
}