细菌(disease)
题目大意：
近期，农场出现了D (1<= D <=15)种细菌。John 要从他的 N (1<= N <=1,000)头奶牛中尽可能多地选些产奶。但是如果选中的奶牛携带了超过 K (1<= K <=D)种不同细菌，所生产的奶就不合格。请你帮助John 计算出最多可以选择多少头奶牛。
输入样例：
6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
输出样例：
5
样例说明：
选择：1,2,3,5,6 。只有1#和2#两种细菌。
解题思路：
这道题可以枚举，但1<= N <=1000，N太大，不可能枚举N，所以就枚举细菌。一共有2^D种情况，每次判断有多少头牛符合标准，然后求一个最大值。实现方法可以是深度搜索，也可以用位操作。
参考程序1：
# include <iostream>
# include <stdio.h>
using namespace std;
const int maxN=1000+5;
int n,d,nk,g[maxN],a[maxN][20],ans;
bool f[20];
void find(int k,int s)
{
if (s>nk) return;
if (k>=d)
{
if (s<nk) return;
int s=0;
for (int i=0; i<n; i++)
{
bool flag=true;
for (int j=0; j<g[i]; j++)
if (!f[a[i][j]]) {flag=false; break; }
if (flag) s++;
} // 判断有多少头牛合法
ans=max(ans,s); // 求最大值
return;
}
f[k]=true;
find(k+1,s+1); // 取
f[k]=false;
find(k+1,s); // 不取
}
int main()
{
cin>>n>>d>>nk;
for (int i=0; i<n; i++)
{
cin>>g[i];
for (int j=0; j<g[i]; j++) cin>>a[i][j];
}
ans=0;
find(0,0); // 深度搜索
cout<<ans<<endl;
return 0;
}
参考程序2：# include <iostream>
# include <stdio.h>using namespace std;
const int maxN=1000+5;
int n,d,nk,a[maxN],ans,g;int main()
{
cin>>n>>d>>nk;
for (int i=0; i<n; i++)
{
cin>>g;
for (int j=0; j<g; j++)
{
int c;
cin>>c;
a[i]+=1<<(c-1); // 把输入变成二进制，1表示有这一种细菌，0表示没有这一种细菌
}
}
ans=0;
for (int i=0; i<(1<<d); i++)
{
int k=0,t=i;
while (t!=0)
{
if (t & 1==1) k++;
t/=2;
}// 求细菌的个数
if (k>nk) continue; // 判断是否合法
int s=0;
for (int j=0; j<n; j++)
{
int c=i | a[j];
if (c==i) s++;
} // 求有多少头牛合法
ans=max(ans,s); // 求最大值
}
cout<<ans<<endl;
return 0;
}