枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。
枚举结构:循环 + 判断语句。
虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件:
⑴可预先确定每个状态的元素个数 n;
⑵状态元素 a1,a2,…,an 的可能值为一个连续的值域。
设 ai1—状态元素 ai 的最小值;aik—状态元素 ai 的最大值 (1≤i≤n),即 a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank
- 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 状态(a1,…,ai,…,an)满足检验条件
- then 输出问题的解;
枚举法的优点:
⑴由于枚举算法一般是现实生活中问题的 "直译",因此比较直观,易于理解;
⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上,所以算法的正确性比较容易证明
枚举法的缺点:
枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。
直译 " 枚举:直接根据题意设定枚举对象、范围和约束条件。
注意认真审题,不要疏漏任何条件
例题 1:砝码称重
【问题描述】设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚(其总重 <=1000),求用这些砝码能称出不同的重量个数。
【文件输入】输入 1g、2g、3g、5g、10g、20g 的砝码个数。
【文件输出】输出能称出不同重量的个数。
【样例输入】1 1 0 0 0 0
【样例输出】3
【分析】根据输入的砝码信息,每种砝码可用的最大个数是确定的,而且每种砝码的个数是连续的,能取 0 到最大个数,所以符合枚举法的两个条件,可以使用枚举法。枚举时,重量可以由 1g,2g,……,20g 砝码中的任何一个或者多个构成,枚举对象可以确定为 6 种重量的砝码,范围为每种砝码的个数。判定时,只需判断这次得到的重量是新得到的,还是前一次已经得到的,即判重。由于重量 <=1000g,所以,可以开一个 a[1001] 的数组来判重。
C++ 代码如下:
- #include using namespace std;
- int A[1001] = {
- 0
- };
- int main() {
- int a,
- b,
- c,
- d,
- e,
- f,
- i,
- sum,
- num;
- int arr[7];
- int w[7] = {
- 0,
- 1,
- 2,
- 3,
- 5,
- 10,
- 20
- };
- 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 < endl;
- return 0;
- }
例题 2:火柴棒等式
【问题描述】给你 n 根火柴棍,你可以拼出多少个形如 "A+B=C" 的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0)。用火柴棍拼数字 0-9 的拼法如图所示:
注意:
1. 加号与等号各自需要两根火柴棍
2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C≥0)
3. n 根火柴棍必须全部用上
【输入】输入一个整数 n(n≤24)。
【输出】输出能拼成的不同等式的数目。
问题简述:给你 n(n<=24) 根火柴棒, 叫你拼出 "A + B = C" 这样的等式, 求方案数。
思路:本题最多 24 根火柴,等号和加号共用 4 根火柴,所以 A,B,C 这 3 个数字需用 20 根火柴。我们考查 A 和 B 的最大的取值可能:0~9 这 10 个数字所用的火柴数为 6,2,5,5,4,5,6,3,7,6,很明显数字 1 用的火柴棒最少只要 2 根,不妨让 B 为 1,那么 A 和 C 最多可以使用 18 根火柴,而 C>=A,满足条件的 A 的最大取值为 1111。所以枚举 A 和 B 的范围是从 0~1111。
为了加快速度,可以将 0 到 2222 的所有整数需要的火柴棒数目提前算好保存在数组中。代码如下:
- #include using namespace std;
- int a[2223] = {
- 6,
- 2,
- 5,
- 5,
- 4,
- 5,
- 6,
- 3,
- 7,
- 6
- };
- const int b[10] = {
- 6,
- 2,
- 5,
- 5,
- 4,
- 5,
- 6,
- 3,
- 7,
- 6
- };
- //计算自然数n所需要的火柴数
- 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; i++) //预处理
- 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 < endl;
- system("PAUSE");
- return 0;
- }
枚举算法的时间复杂度:状态总数 * 单个状态的耗时。
⑴提取有效信息;
⑵减少重复计算;
⑶将原问题化为更小的问题;
⑷根据问题的性质进行截枝;
⑸引进其他算法
【例题 3】给你 n(n<=105) 个整数,然后要有 m (m<=105) 个询问。每个询问两个整数 i 和 j,问第 i 个数字到第 j 个数字所有数字之和。
朴素算法:
- #include 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 < endl;
- }
- return 0;
- }
优化算法:
先计算 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 < 1] << endl;
- }
【例题 4】最大子矩阵问题
【问题描述】给定一个二维的数组(含正数或负数),请从中找出和最大的子矩阵。例如:
方法 1:"直译" 枚举过程
- for(x1=1;x1<=n;x1++)//枚举矩形左上角(x1,y1)
- for(y1=1;y1<=n;y1++)
- for(x2=1;X2<=n;X2++)//枚举矩形右下角(x2,y2)
- for(y2=1;y2<=n;y2++)
- 考察状态左上角为(x1,y1)右下角为(x2,y2)内矩形的元素之和;
设 map 为数字矩阵;sum 为当前矩形内元素的和;best 为最优解。考察过程如下:
- sum = 0;
- for (x = x1; x <= x2; x++) //计算当前矩形内元素的和
- for (y = y1; y <= y2; y++) sum = sum + map[x][y];
- if (sum > best) best = sum; //调整最优解
这个算法相当粗糙,枚举状态的费用为 O(n6)
方法 2:从减少重复计算入手
有刚才一维情况可以推广到二维,在统计左上角为 (x1,y1) 右下角为 (x2,y2) 内矩形的元素之和时,我们同样可以先初始化,计算出左上角为 (1,1) 右下角为 (x,y) 内矩形的元素之和 s[x][y]。
- for(x1=1;x1<=n;x1++)//枚举矩形左上角(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];
- }
- }
对于状态左上角为 (x1,y1) 右下角为 (x2,y2) 内矩形的元素之和,可以改为:
- sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
- if (sum > best) best = sum; //调整最优解
由于利用了计算出的结果,整个算法的时间复杂度降为 O(n4)
方法 3:提取恰当的信息
容易观察到,最大子矩阵问题是最大连续子序列和问题的提升,即将一条线换成一个面,将一维问题提升到二维问题。所以我们计算最大子矩阵的方法就是将一行行的数进行累加以求得最大值。
但是还有一个问题,那就是应该如何高效地存储矩阵?
我们可以想到:在一个一维的数列中,设数组 b[i] 表示从第 1 个元素到第 i 个元素的和,则如果想要求第 i 个元素到第 j 个元素的和,只需要计算 b[j]-b[i-1] 的值就行了。由此推广到二维矩阵,设 b[i][j] 表示矩阵第 j 列前 i 个元素的和,a[i][j] 表示元素数据,则压缩存储:
- 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];
- }
因此,我们可以使用三重循环求出所有的矩形值,即枚举起始行 i 和终止行 j,压缩子矩形成为一行,变成一维求最大字段和问题。
即 t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];
时间复杂度为 O(n3)
核心代码:
- sum=-0x7fffffff;
- for(i=1;i<=n;i++) //阶段:起始行
- {
- for(j=i;j<=n;j++) //状态:结束行
- {
- t[1]=b[j][1]-b[i-1][1]; //初始化第1列的值
- for(k=2;k<=n;k++) //决策:第几列
- {
- t[k]=max(t[k-1],0)+b[j][k]-b[i-1][k];
- if(t[k]>sum)sum=t[k];
- }
- }
- }
- cout<<sum<<endl;
来源: http://www.cnblogs.com/ECJTUACM-873284962/p/6445989.html