一般而言，对类组合数问题，朴素的枚举法实现中，往往有几个未知的东西，我们就来几重循环。再根据提议处理循环范围，在最里层的循环中加入判断语句，判断该组合是否满足条件。

​ 枚举对象一多，就会写出比较复杂的代码，时间效率也不太优秀。
pdf

常见枚举优化思路

• 减少枚举对象
• 剪枝

减少枚举对象

​ 可以利用数学性质来进行对象的优化。例如有三个未知的对象，限制条件为总量固定为N，按以往的处理可以写出三重循环，每重循环的范围限制0~N。复杂度就为$O(N^3)$。

​ 若我们确定了前两个数的个数i,j。第三个数利用总量固定的特性，可求出第三个数的数量：N-i-j 。那么就只需写出两重循环，复杂度可降为$O(N^2)$。

剪枝

​ 对于当前分支已经明显不可能满足条件的话，可以直接结束当前分支，思考另一种分支。

hash优化

​ 对于每个数字是否存在，除了对所有的数字进行遍历，依次判断以外，在数字范围不太大的前提下，可以利用hash的思想简化判断过程。将遍历的$O(n)$降为调用的$O(1)$。

例题讲解

2022数对

方法1

朴素枚举,复杂度为$O(n^2)$

#include <iostream>
using namespace std;
const int N=1e4+5;
int a[N];//存储不同的整数
int main(){
    int n,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];//输入n个数字
    }
    for(int i=1;i<=n;i++){//遍历第1个数字
        for(int j=i+1;j<=n;j++){//遍历第2个数字，为了避免重复，设定下标从j+1开始
            if(a[i]+a[j]==2022){//判断 数对和 是否满足要求
                cnt++;//统计个数
            }
        }
    }
    cout<<cnt;//输出答案
    return 0;
}

方法2

优化。复杂度$O(n)$

数值范围是$[-10000,10000]$ 。范围不太大，可以将值映射到下标，用于判断某个值是否出现。注意下标最小从0开始，所以映射的范围为$[0,20000]$ 只需将输入的值$+10000$即可实现偏移映射。

cin>>x;
vis[x+10000]=1;

已知总和为2022

当输入x，若能组合形成数对，另一个数值确定为2022-x。

只需判断这个数在之前出现过没即可。

#include<iostream>
using namespace std;
const int N=1e4+5;
bool vis[2*N];
int main(){
    int n,x,cnt=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        int y=2022-x;//求能形成数对的另一个可能值
        if(y>=-10000&&y<=10000&&vis[y+10000]){//另一个数在范围内，且该数在之前出现过
            cnt++;
        }
        vis[x+10000]=true;//标记x对应的数出现过
    }
    cout<<cnt;//输出答案
    return 0;
}

珠心算测验

方法1

朴素枚举，复杂度$O(n^3)$。

#include <iostream>
#include <algorithm>
using namespace std;
int n,cnt;
int a[105];
bool sum[30005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);//从小到大到排序
    for(int i=1;i<=n;i++){//找第一个数
        for(int j=i+1;j<=n;j++){//找第二个数
            for(int k=j+1;k<=n;k++){//找第三个数 和
                if(a[i]+a[j]==a[k]&&!sum[a[k]]){//hash判断，防止重复
                    sum[a[k]]=true;
                    cnt++;
                }
            }
        }
    }
    cout<<cnt;
    return 0;
}

方法2

将所有的两个数字的组合对应的和进行标记。再看输入的数字中是否有被标记过的和，进行统计即可。

复杂度$O(n^2)$

#include <iostream>
using namespace std;
int n,cnt;
int a[105];
bool sum[20005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=1;j<i;j++){//与之前的1~i-1的数进行组合
            sum[a[i]+a[j]]=true;//将组合的和进行标记
        }
    }
    for(int i=1;i<=n;i++){//遍历输入的数，统计是集合中其他两个数的和的个数
        if(sum[a[i]]) cnt++;
    }
    cout<<cnt;
    return 0;
}

砝码称重

方法1

枚举每种砝码的可能的使用个数，6种砝码就是6重循环。

复杂度$O(x_1\times x_2\times x_3\times x_4\times x_5 \times x_6)$

#include<iostream>
using namespace std;

int num[7];
int w[1001];

int main() {
    int i, j, k, l, m, n, cnt = 0, sum;
    //按照顺序输入不同砝码的数量
    for (i = 1; i <= 6; i++) {
        cin >> num[i];
    }
    //进行数量枚举
    for (i = 0; i <= num[1]; i++) {
        for (j = 0; j <= num[2]; j++) {
            for (k = 0; k <= num[3]; k++) {
                for (l = 0; l <= num[4]; l++) {
                    for (m = 0; m <= num[5]; m++) {
                        for (n = 0; n <= num[6]; n++) {
                            if (i + j + k + l + m + n >= 1) {
                                sum = i * 1 + j * 2 + k * 3 + l * 5 + m * 10 + n * 20;
                                w[sum] = 1;//标记总和
                            }
                        }
                    }
                }
            }
        }
    }
    //找1~1000中能称出来的重量
    for (i = 1; i <= 1000; i++) {
        if (w[i] == 1) {//判断重量i是否能被砝码表示
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

方法2

hash结合背包的思路。

每次你使用一个砝码就在之前的砝码组合出的重量上再放一个，标记新重量为可组合的。

需要注意的是，当前状态只能由之前的状态决定，你当前能组合的重量基于你之前可组合出的重量。所以遍历重量时从大到小来，因为新重量总是在原来的组合出的重量上增加砝码，重量总是增加的，从小到大的话，会影响之后的判断。

复杂度$O(x\times m)$ x-个数，m-总重量

#include <iostream>
#include <cstring>
using namespace std;
bool wei[1005];
int num[10]={0,1,2,3,5,10,20};
int main(){
    int x,ans=0;
    for(int i=1;i<=6;i++){
        cin>>x;
        for(int j=1;j<=x;j++){
            for(int k=1000;k>=0;k--){//注意顺序 以免组合出的新重量，影响之后的处理
                if(wei[k]){//之前已经能组合出重量k
                    wei[k+num[i]]=true;//在之前的基础上，再加一个砝码形成新重量k+num[i]
                }
            }
            if(j==1){
                wei[num[i]]=true;//标记num[i]能表示的重量
            }
        }
        
    }
    for(int i=0;i<=1000;i++){//遍历总重量范围内所有的可表达的重量
        ans+=wei[i];
    }
    cout<<ans;
    return 0;
}