暴力枚举巧优化：枚举算法

枚举法，也称为穷举法，是在全部的可能性中，搜索可行解或最优解。因为解是不确定的，需要尝试所有可能性，即按照一定顺序，不重复、不遗漏地逐个尝试。枚举法虽然需要消耗大量的时间，但是思路和编程都非常简单，保证可以取得正确结果。也被称为暴力（Brute-Force）算法。

预习篇

枚举法的本质就是从所有候选答案中去搜索正确的解，可以使用循环语句和条件判断语句逐步验证候选答案的正确性，从而得到需要的正确答案。看看下面的例子：

• 在1到100的正整数中，有多少个数字是2的倍数？

1. 循环

显然学过循环的我们知道，可以通过定义一个循环变量 i 来枚举1-100中所有数字，并使用计数器变量cnt来统计满足条件的数字个数：

int cnt = 0;
for (int i = 1; i <= 100; i++) {
    int t = i; //先把i存下来，不要随便在循环体改变循环变量的值哦
    如果t是2的倍数，那么
        cnt++;        
}
printf("%d", cnt);

2. 条件判断

怎么判断 t 是不是2的倍数？你一定知道要怎么做~

xxxxxxxxxx
// 使用条件判断语句看看t是不是偶数
    if (t % 2 == 0) 

来个简单的练习试一试：

• 填数字

上面这道题使用两层循环实现对两个数字的枚举。如果有三个数要填呢？答案是三层循环。如果有更多个需要枚举的对象，往往需要使用更多层循环，这样程序运行的时间也会增加。所以，对于枚举算法，我们往往会采用一些优化的方法，例如，使用尽可能少的枚举对象以减少循环层数；每一层循环中精确循环变量的取值范围以减少循环次数等等。

课后篇

现在你应该对枚举算法有了初步了解，可以尝试解决下面这个问题：

用100元钱兑换面值为1元、2元、5元的纸币共50张，每种纸币不少于一张，求出每种兑换方案中1元、2元、5元的纸币各有多少张？共有多少种兑换方案？

最直观的方法如下：

一、枚举三种纸币数量，使用三层循环

xxxxxxxxxx
//x表示1元纸币张数，y表示2元纸币张数，z表示5元纸币张数
//s表示方案数
int main(){
    int x, y, z, s = 0; 
    for(x = 1; x <= 50; x++){
        for(y = 1; y <= 50; y++){
            for(z = 1; z <= 50; z++){
                if(x + y + z == 50 && 
                   x + 2 * y + 5 * z == 100){
                        printf("%d %d %d\n", x,y,z);
                }
                s++;
            }
        }
    }
    printf("%d", s);
    return 0;
}

上面的解法非常直观，但通过题目描述中给定的条件，即三种纸币数量之和为50，我们发现其实可以减少一个枚举对象。于是有了下面的做法：

二、枚举两种纸币数量，计算第三种数量，使用两层循环

xxxxxxxxxx
//x表示1元纸币张数，y表示2元纸币张数，z表示5元纸币张数
//s表示方案数
int main(){
    int x, y, z, s = 0; 
    for(x = 1; x <= 50; x++){
        for(y = 1; y <= 50; y++){
            z = 50 - x - y;
                if(x + 2 * y + 5 * z == 100){
                        printf("%d %d %d\n", x,y,z);
                }
                s++;
            }
        }
    }
    printf("%d", s);
    return 0;
}

三、缩小循环范围

还能进一步优化吗？能！

虽说总张数是50，其实每一种纸币取不到50张。例如：1元钱的最多能取43张。为什么？每种至少有一张，除去一张2元和一张5元，全部是1元也就能取43张。

另外，我们枚举5元的张数和枚举两元的张数是不是比枚举1元的张数和枚举2元的张数循环的次数更少呢？

相信聪明的你一定有了自己的答案。

​x
//x表示1元纸币张数，y表示2元纸币张数，z表示5元纸币张数
//s表示方案数
int main(){
    int x, y, z, s = 0;
    for(y = 1;______; y++){
        for(z = 1;______; z++){
            x =______;
            if(______){
                printf("%d %d %d\n", x, y, z);
            }
        }
    }
    cout << s << endl;
    return 0;
}

提高篇

一、补充练习

二、真题重现

2.1 砝码称重 [NOIP1996 提高组]

题目描述

设有 $1\mathrm{g}$$1\mathrm{g}$、$2\mathrm{g}$$2\mathrm{g}$、$3\mathrm{g}$$3\mathrm{g}$、$5\mathrm{g}$$5\mathrm{g}$、$10\mathrm{g}$$10\mathrm{g}$、$20\mathrm{g}$$20\mathrm{g}$ 的砝码各若干枚（其总重$\le 1000$$\le 1000$），可以表示成多少种重量？

输入格式

$a_1,a_2,a_3,a_4,a_5,a_6$$a_1 , a_2 ,a_3 , a_4 , a_5 ,a_6$

（表示 $1\mathrm{g}$$1\mathrm{g}$ 砝码有 $a_1$$a_1$ 个，$2\mathrm{g}$$2\mathrm{g}$ 砝码有 $a_2$$a_2$ 个，…，$20\mathrm{g}$$20\mathrm{g}$ 砝码有 $a_6$$a_6$ 个）

输出格式

Total=N

（$N$$N$ 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

样例输入 #1

xxxxxxxxxx
1 1 0 0 0 0

样例输出 #1

xxxxxxxxxx
Total=3

提示

• 快去挑战一下！砝码称重

2.2 三连击 [NOIP1998 普及组]

题目背景

本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。

题目描述

将 $1,2,\dots ,9$$1, 2, \ldots , 9$ 共 $9$$9$ 个数分成 $3$$3$ 组，分别组成 $3$$3$ 个三位数，且使这 $3$$3$ 个三位数构成 $1:2:3$$1 : 2 : 3$ 的比例，试求出所有满足条件的 $3$$3$ 个三位数。

输入格式

无

输出格式

若干行，每行 $3$$3$ 个数字。按照每行第 $1$$1$ 个数字升序排列。

样例输入 #1

xxxxxxxxxx
无

样例输出 #1

xxxxxxxxxx
192 384 576
* * *
...

* * *
（剩余部分不予展示）

• 快去挑战一下！三连击

拓展篇

一、赛场上的应用

验证复杂的程序的正确性，可写功能一致的暴力对照程序，并构 造小规模输入数据，比较二者输出。这一过程称作对拍，在赛场上是非常实用的查错技巧。

二、其他枚举类型