最近两天状态不佳……所以刷的题目并不多。让人更悲伤的其实还是，大部分是水题。。
但是刷完这道题的时候意识到不能这么水下去了~所以决定深入研究一下子集生成，当然啦，是基于刘汝佳老师的算法入门经典，这里只是将其加以应用，仅此而已。
一、首先是我个人认为最好理解的子集生成方法——位向量法：
#include <cstdio>
#include <cstring>
using namespace std;
int a[110][25];
char s[110][25];
int flag[25];
int min_;
int p,n;
int subset(int n,int p,int cur)
{
if(cur==p)
{
int ct=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<p;j++)
{
if(flag[j])
{
ct++;
s[i][j]=a[i][j]+‘0‘;
}
else
s[i][j]=0+‘0‘;
}
}
for(int i=0;i<n;i++)
{
s[i][p]=0;
}
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(!strcmp(s[i],s[j]))
return 0;
}
}
if(min_>ct/n)
min_=ct/n;
return 0;
}
flag[cur]=0;
subset(n,p,cur+1);
flag[cur]=1;
subset(n,p,cur+1);
return 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(flag, 0, sizeof(flag));
scanf("%d%d",&p,&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<p;j++)
scanf("%d",&a[i][j]);
}
min_=p;
subset(n,p,0);
printf("%d\n",min_);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int maxn=110;
int B[maxn][20],min,A[20],n,p;
int is_ok(int cur)//这里是根据题目要求来的。
{
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
int ok=1;
for(int k=0;k<cur;k++)
if(B[i][A[k]]!=B[j][A[k]]) {ok=0;break;}
if(ok) return 0;
}
return 1;
}
void try_subset(int cur)//这个函数就是用来实现增量构造法的。判断合不合适用的是上面的函数is_ok()。
{
if(min>cur &&is_ok(cur)) min=cur;
int s=cur?A[cur-1]+1:0;
for(int i=s;i<p;i++)
{
A[cur]=i;
try_subset(cur+1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&p,&n);
int i,j;
for(i=0;i<n;i++)
for(j=0;j<p;j++)
scanf("%d",&B[i][j]);
min=15;
try_subset(0);
printf("%d\n",min);
}
return 0;
}
三、是高大上威武雄壮的——二进制法：
介个……理解是不难，但真的要自己运用起来恐怕不会那么容易。
这个自己不会用，要多解释一番：
#include <cstdio>
#include <cstring>
const int P = 1 << 15, maxn = 105;
bool vis[P + 5];
int a[maxn];
int count(int n)//统计n的二进制中1的个数
{
int sum = 0;
while (n)
{
if (n & 1)//和1做与运算，不停右移直到为零。如果最右位为一，则sum会加1；
++sum;
n >>= 1;
}
return sum;
}
int main()
{
int t, p, n, x, i, j, ans, up;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &p, &n);
for (i = 0; i < n; i++)
{
scanf("%d", &a[i]);
for (j = 1; j < p; j++)
{
scanf("%d", &x);
a[i] = (a[i] << 1) + x;//把所给出的0和1的串压缩成一个数字，此处的p不能太大，否则可能会溢出。
//其实这个地方是和上面统计1的个数相对应的，只不过用右移左移运算对电脑来说更容易，更能节省时间。
}
}
ans = p, up = 1 << p;
for (i = 0; i < up; i++)//枚举,从0开始枚举到2的p次方减1.你知道一个有n个元素的集合有2的n次方个子集的；
{
int bits = count(i);
if (bits >= ans) continue;//比当前最小结果大的时候就不用继续判断了，不符合。
memset(vis, 0, sizeof(vis));
for (j = 0; j < n; ++j)
{
int pos = a[j] & i;//a[j]在i下的显示结果（这能确定两个数相同的位的个数和相同位的位置——形成的数是唯一的）
if (vis[pos])//说明有两个数显示是一样的
break;
vis[pos] = true;
}
if (j < n) continue;
ans = bits;
}
printf("%d\n", ans);
}
return 0;
}
uva 11205 The Broken Pedometer（经典的子集生成题目，在此总结了三种子集生成的方法~）,布布扣,bubuko.com
uva 11205 The Broken Pedometer（经典的子集生成题目，在此总结了三种子集生成的方法~）
原文：http://blog.csdn.net/u013382399/article/details/23516051