抗震机械制造
Time Limit:1000MS Memory Limit:65536KB
Total Submit:312 Accepted:78
Description
为了应付可能到来的地震，ECNU国国王CS决定花大量资金开发几种矿藏来制造各种救援机械。矿藏一旦被开发就可以无限使用。为了使自己的救援队能应付尽可能多的境况，CS决定让自己的救援队的机械组成尽量多元化。CS数学太弱，面对复杂的机械制造数据，他只好求助于你。
如果CS给你关于机械制造的具体数据，你能帮他计算出他最多能制造多少种救援机械吗？
Input
测试数据以一个整数T(1<=T<=20)开头，表示有T组测试数据。
每组测试数据都以三个整数n(1<=n<=100),m(1<=m<=16),p(1<=p<=16000)开始，n表示可以制造的机械的种数，m表示矿藏的种数，p表示CS最多能花费的资金。
接下来一行有m个整数，第i个整数表示开发第i种矿藏需要的资金。
然后有n行，每行m个数（1或0），第i行第j个数为"1"表示制造第i种机械需要第j种矿藏，若为"0"则表示不需要。
Output
对于每组测试数据，输出CS最多能制造的机械的种数。
Sample Input
2
3 4 1719
409 626 785 108
0 0 0 0
1 0 1 1
1 0 0 0
3 4 1612
268 223 480 947
1 1 1 0
1 1 1 1
0 0 1 0
Sample Output
3
2
Hint:
Case1:开发1，3，4号矿藏即可制造所有的机械，总开销为409+785+108=1302
Case2:开发1，2，3号矿藏即可制造第一种和第三种机械，总开销为268+223+480=971，因为制造第二种机械需要开发第四种矿藏，需要再花费947，超出上限，所以无法达到。
Source
解题：一道暴力枚举题
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,m,p,ret; 4 int cost[20],need[110]; 5 void check(int x){ 6 int sum = 0; 7 for(int i = 0; i < n; ++i) 8 if((need[i]&x) == need[i]) sum++; 9 if(sum > ret) ret = sum; 10 } 11 int main(){ 12 int kase,tmp; 13 scanf("%d",&kase); 14 while(kase--){ 15 scanf("%d%d%d",&n,&m,&p); 16 for(int i = 0; i < m; ++i) 17 scanf("%d",cost+i); 18 for(int i = 0; i < n; ++i){ 19 need[i] = 0; 20 for(int j = 0; j < m; ++j){ 21 scanf("%d",&tmp); 22 if(tmp) need[i] |= (1<<j); 23 } 24 } 25 ret = 0; 26 for(int i = 1; i < (1<<m); ++i){ 27 int sum = 0; 28 for(int j = 0; j < m; ++j) 29 sum += ((i>>j)&1)*cost[j]; 30 if(sum > p) continue; 31 else check(i); 32 } 33 printf("%d ",ret); 34 } 35 return 0; 36 }