二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。利用二进制的特点,可以用于枚举一个集合中各元素的所有组合情况。
例如,设某集合M中有3个元素A、B和C,即M={A,B,C}。可以用3位二进制数来枚举3个元素的各种组合情况(也可以称为子集),每一位二进制数字对应一个元素,1表示选中,0表示不选。
二进制数 001,表示选中A元素,B和C元素不选择,即子集为 { A };
二进制数 010,表示选中B元素,A和C元素不选择,即子集为 { B };
二进制数 011,表示选中A和B元素,C元素不选择,即子集为 { A,B };
二进制数 100,表示选中C元素,A和B元素不选择,即子集为 { C };
二进制数 101,表示选中A和C元素,B元素不选择,即子集为 { A,C };
二进制数 110,表示选中B和C元素,A元素不选择,即子集为 { B,C };
二进制数 111,表示选中A、B和C这3个元素均选中,即子集为 { A,B,C };
当然,二进制数000表示3个元素均不选择,就是子集是空集。
这样,用循环 for (int i = 0; i < (1 << n); i++) 就可以遍历每一个子集,即遍历各种组合情况。其中 (1 << n)表示 2n ,2n-1就对应n为二进制数,各位上的数字均为1。
然后,可以利用二进制的位运算,来判断二进制数的某一位上是0还是1。
二进制位运算的左移运算 a << b就表示把a转为二进制后左移b位(即在后面添b个0)。
这样, 1<<0=1(0) ; 1<<1=2 (10); 1<<2=4 (100); 1<<3=8 (1000);
……
因此,要判断一个二进制数x的第k位上是0还是1,只需计算 x & (1<<K),若计算出来的值为0,则x的第k位为0;若计算出来的值非0,则x的第k位为0。
这样,再利用循环
For (int j = 0; j < n; j++)
if (i & (1 << j)) { … }
就可以对每一个子集中所选取的具体元素进行处理。
编写如下的示例程序。
#include <stdio.h> int main() { char s[6]="ABCDE"; int n; scanf("%d",&n); int i,j; for (i=0; i<(1<<n); i++) // 枚举从0~2^n-1中组合情况 { printf("[ "); for (j = 0; j < n; j++) // 遍历二进制的每一位 { if (i & (1 << j)) // 判断二进制第j位是否为1,若为1,表示元素选中 { printf("%c ",s[j]); // 如果第j个元素选中,则输出 } } printf("]n"); } return 0; }
该程序运行后,输入3,可以输出A、B、C这3个元素的8中组合情况。运行结果如下所示。
下面通过一些实例来看二进制枚举的应用方法。
【例1】最接近的和
问题描述
给出两个整数n(n≤20)和b,然后给出n个整数h1、h2、…、hn。问如何在这n个整数里面选择若干个数使得它们的和在满足大于等于b的情况下最小,并输出这个和与b的差。
输入
第1行:2个用空格隔开的整数:N和B。
第2…N+1行:第i+1行是1个整数:Hi。
输出
输出1个非负整数,即满足大于等于b的情况下的最小和值与b的差。
输入样例
5 16
3
1
3
5
6
输出样例
1
(1)编程思路。
直接套用上面的二进制枚举的模板对h1、h2、…、hn这n个元素的各种组合情况进行处理。只是在具体处理时,将每次挑选中的元素累加起来。当和值大于等于b时,记录最小的和值即可。
(2)源程序。
#include <stdio.h> int main() { int n,b; scanf("%d%d",&n,&b); int i,j,h[21]; for (i=0;i<n;i++) scanf("%d",&h[i]); int ans=0x3f3f3f3f; for (i=0; i<(1<<n); i++) // 枚举从0~2^n-1中组合情况 { int sum=0; for (j = 0; j < n; j++) // 遍历二进制的每一位 { if (i & (1 << j)) // 判断二进制第j位是否为1,若为1,表示元素选中 { sum+=h[j]; // 如果第j个元素选中,则加上它 } } if (sum>=b) { if (sum<ans) ans=sum; } } printf("%dn",ans-b); return 0; }
将上面的源程序提交给 洛谷题库 P2677 [USACO07DEC]Bookshelf 2 B(https://www.luogu.com.cn/problem/P2677),可以Accepted。
【例2】权利指数
问题描述
在选举问题中,总共有n个小团体,每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半,则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是:在其所在的获胜联盟中,如果缺少了这个小团体的加入,则此联盟不能成为获胜联盟。一个小团体的权利指数是指:一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。
输入
输入数据的第一行为一个正整数T,表示有T组测试数据。每一组测试数据的第一行为一个正整数n(0<n<=20)。第二行有n个正整数,分别表示1到n号小团体的票数。
输出
对每组测试数据,在同一个行按顺序输出1到n号小团体的权利指数。
输入样例
2
1
10
7
5 7 4 8 6 7 5
输出样例
1
16 22 16 24 20 22 16
(1)编程思路。
同样直接套用上面的二进制枚举的模板对n个小团体的各种组合情况进行处理。若某个团体组合的得票数超过了总票数的一半,则依次对该组合中的每个小团队进行判断,若去掉了某个小团体后,得票数小于总票数的一半,则去掉的小团体就是关键加入者,进行计数。
(2)源程序。
#include <stdio.h> #include <string.h> int main() { int t; scanf("%d", &t); while (t--) { int a[21],key[21], ans[21]; memset(ans, 0, sizeof(ans)); int n,total = 0; scanf("%d", &n); int i; for (i = 0; i < n; i++) { scanf("%d", &a[i]); total += a[i]; } total /= 2; for (i = 1; i < 1 << n; i++) // 二进制枚举各团体组合 { int j, k = 0, sum = 0; for (j = 0; j < n; j++) // 遍历二进制的每一位 { if (i & (1 << j)) // 判断二进制第j位是否为1 { key[k++] = j; sum += a[j]; } } if (sum > total) // 如果团体的票数超过总票数的一半 { for (j = 0; j < k; j++) if (sum - a[key[j]] <= total) // 编号为key[j]的元素为 关键加入者 ans[key[j]]++; } } printf("%d", ans[0]); for (i = 1; i < n; i++) printf(" %d", ans[i]); printf("n"); } return 0; }
将上面的源程序提交给 HDU题库 HDU 1557 权利指数(http://acm.hdu.edu.cn/showproblem.php?pid=1557),可以Accepted。
【例3】目标和习惯
问题描述
小明有很多习惯,比如看电影、听音乐、玩电脑游戏和足球等等。此外,他还有很多目标,因为不是每个习惯都有助于实现他的目标,他陷入了在目标和习惯之间做出选择的困境。
现在,我们将一个习惯对每个目标的影响定义为向量,向量的元素是整数,例如。向量(100,90,-10,80)表示它对目标1有100分的影响,对目标2有90分的影响、对目标3有-10分的影响和对目标4有80分的影响(正表示良好效果,负表示不良效果),每个目标的给定要求表示为整数。请帮助小明实现他的目标,并尽可能多地保持他的习惯。
输入
有多种情况,读取数据直到EOF。(不超过10例)
第1行:小明的目标数N(0<N<=20)
第2行:每个目标的要求(0<w<=1000)
第3行:小明的习惯数M(0<M<=16)
第4-M+4行:每行包含N个整数,第i个整数表示对第i个目标的影响(-1000<=data<=1000)。
输出
对于每种情况:输出是一行,其中包含:
小明可以保持的最大习惯数,其次是:
小明可以保持的习惯的排序列表(从最小到最大)。如果有一组以上的习惯可以满足要求,请选择习惯数最少的一组。
如果无法实现小明的目标,请输出0。
输入样例
4
100 200 300 400
3
100 100 400 500
100 -10 50 300
100 100 -50 -50
输出样例
2 1 3
(1)编程思路。
采用二进制枚举对m个习惯的全部组合情况进行处理。对每种习惯组合,将组合中的各习惯对目标的影响累加到数组g中。若数组g中每个目标均可实现,则是一种满足要求的习惯组合。
(2)源程序。
#include <stdio.h> #include <string.h> int main() { int goal[21]; int f[17][21],g[21]; int n; while (scanf("%d",&n)!=EOF) { int ans1=-1,ans2; int i,j,k; for (i=0;i<n;i++) scanf("%d",&goal[i]); int m; scanf("%d",&m); for (i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&f[i][j]); for (i=0;i<(1<<m);i++) // 对所有m个习惯的组合进行枚举 { for (k=0;k<n;k++) g[k]=0; // 各目标的达到值初始化为0 int num=0; // 当前组合中的习惯个数 for (j=0;j<m;j++) if (i&(1<<j)) // 若组合中有第j个习惯 { num++; for (k=0;k<n;k++) // 第j个习惯对每个目标k的影响 g[k]+=f[j][k]; } for (k=0;k<n;k++) if (g[k]<goal[k]) break; // 第k个目标不能实现 if (k==n) // 当前习惯组合中,所有目标可达成 { if (num>ans1) { ans1=num; ans2=i; } } } if (ans1==-1) printf("0n"); else { printf("%d",ans1); for (i=0;i<n;i++) if (ans2&(1<<i)) printf(" %d",i+1); printf("n"); } } return 0; }
将上面的源程序提交给 HDU题库 HDU 4152 ZZY’s Dilemma(http://acm.hdu.edu.cn/showproblem.php?pid=4152),可以Accepted。
【例4】调查问卷
问题描述
度度熊为了完成毕业论文,需要收集一些数据来支撑他的论据,于是设计了一份包含 m 个问题的调查问卷,每个问题只有 'A' 和 'B' 两种选项。
将问卷散发出去之后,度度熊收到了 n 份互不相同的问卷,在整理结果的时候,他发现可以只保留其中的一部分问题,使得这 n 份问卷仍然是互不相同的。这里认为两张问卷是不同的,当且仅当存在至少一个被保留的问题在这两份问卷中的回答不同。
现在度度熊想知道,存在多少个问题集合,使得这 n 份问卷在只保留这个集合的问题之后至少有 k 对问卷是不同的。
输入
第一行包含一个整数 T,表示有 T 组测试数据。
接下来依次描述 T 组测试数据。对于每组测试数据:
第一行包含三个整数 n,m 和 k,含义同题目描述。
接下来 n 行,每行包含一个长度为 m 的只包含 'A' 和 'B' 的字符串,表示这份问卷对每个问题的回答。
保证 1≤T≤100,1≤n≤103,1≤m≤10,1≤k≤106,给定的 n 份问卷互不相同。
输出
对于每组测试数据,输出一行信息 "Case #x: y"(不含引号),其中 x 表示这是第 x 组测试数据,y 表示满足条件的问题集合的个数,行末不要有多余空格。
输入样例
2
2 2 1
AA
BB
2 2 2
AA
BB
输出样例
Case #1: 3
Case #2: 0
(1)编程思路。
先把每张问卷对10个问题回答的A、B字符串转换成二进制数保存在数组a中,转换时,A转换为1,B转换为0。
采用二进制枚举的方法依次枚举每个可能的子集(选择部分问题的情况,下面将枚举到的某个二进制数i称为当前状态),与每张问卷的这个子集情况(当前状态i)下的答案匹配。具体做法是:将当前状态i与每张试卷的答案(也已转换为了二进制数并保存在数据元素a[j]中)进行与运算,即now=i & a[j],并将cnt[now]加1。显然,若问卷j和问卷k的答案相同,则a[j]与a[k]的值一定相同,这样now的值也相同,cnt[now]的值会加上2。
当匹配到第j张问卷时,第j张问卷与前面的j-1张问卷在当前选择状态i下一定有cnt[i&a[j]]张(包括第j张)的答案相同,也就是有j- cnt[i&a[j]]张的答案存在不同,将它累加到和值sum上。当某个当前状态i与每张问卷匹配完成后,如果和值sum大于或等于k,这种当前状态 i 就是符合题意的一种子集选择。遍历所有可能的子集,就得到最终的答案。
(2)源程序。
#include <stdio.h> #include <string.h> int main() { int t,iCase=0; scanf("%d",&t); while (t--) { int n, m, k; scanf("%d%d%d",&n,&m,&k); int a[1001]; int i,j; for (i=1; i<=n; i++) { char s[15]; scanf("%s",s); int num=0; for (j=0; s[j]!='