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

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

常见枚举优化思路

  • 减少枚举对象
  • 剪枝

减少枚举对象

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

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

剪枝

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

hash优化

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

例题讲解

2022数对

方法1

朴素枚举,复杂度为O(n2)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)O(n)

数值范围是[10000,10000][-10000,10000] 。范围不太大,可以将值映射到下标,用于判断某个值是否出现。注意下标最小从0开始,所以映射的范围为[0,20000][0,20000] 只需将输入的值+10000+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(n3)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(n2)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(x1×x2×x3×x4×x5×x6)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×m)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;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)