二进制枚举(计蒜客幼儿园买玩具)

幼儿园有n 个小朋友，每个小朋友都有自己想玩的玩具。身为幼儿园园长的你决定给幼儿园买一批玩具，由于经费有限，你只能买 $m$ 个玩具。已知玩具商店一共卖 $k$ 种玩具，编号为 $1,2,3,...k$，你让每个小朋友把想玩的玩具编号都写在了纸上。你希望满足尽可能多的小朋友的需求，请计算出最多能满足多少个小朋友的玩具需求。

输入格式

第一行，输入三个整数 $n,m,k(1\le n\le 100,1\le m\le k\le 15)$，中间用空格分开。

接下来 $n$ 行，第 $i+1(0\le i<n)$ 行的第一个数字 a_ia​i​​ 代表第 $i$ 个小朋友想玩的玩具数量，接下来有 a_ia​i​​ 个数字，代表这 a_ia​i​​ 个玩具的编号。

输出格式

输出一个整数，表示最多能满足多少小朋友的玩具需求。

样例输入

5 3 5 2 1 4 0 2 3 1 3 2 3 4 2 4 5

样例输出

3 这道题我的思路是用二进制枚举法，用一个标记数组统计哪些编号的玩具被购买，1为购买，0为不购买，再去统计能满足的孩子数目。 #include <stdio.h> int main(void) { int n, m, k; scanf("%d %d %d", &n, &m, &k); int arr[100][100]; for(int i = 0; i < n; i++) { scanf("%d", &arr[i][0]); for(int j = 1; j <= arr[i][0]; j++) { scanf("%d", &arr[i][j]); } } int max = 0;//最多能满足的孩子数 for(int i = 0; i < (1 << k); i++) { int count = 0;//购买的玩具数 int arrk[16] = {0};//记录玩具是否购买的数组(1为购买) for(int j = 0; j < k; j++) { if(i & (1<<j)) { arrk[j + 1] = 1; count++; } } int count2 = 0;//当前方案能满足的孩子数 for(int x = 0; x < n; x++) { int flag = 1; for(int y = 1; y <= arr[x][0]; y++) { if(arrk[arr[x][y]] == 0) { flag = 0; break; } } if(flag && count <= m) { count2++; } } if(max < count2) { max = count2; } } printf("%d\n", max); return 0; }