2144. 抗震机械制造

二进制遍历

include

using namespace std;
int T,n,m,p;
int price[20];
int need[200];
int ans = 0;
int main()
{
int T;
scanf(“%d”,&T);
while(T–)
{
ans = 0;
scanf(“%d%d%d”,&n,&m,&p);
for(int i = 0;i < m;i = i + 1)
{
scanf(“%d”,&price[i]);
}
for(int i = 0;i < n;i = i + 1)
{
need[i] = 0;
int level = 1;
for(int j = 0;j < m;j = j + 1)
{
int x;
scanf(“%d”,&x);
need[i] = need[i] + x * level;
level = level * 2;
}
}
for(int state = 1;state < (1 << m);state = state + 1)
{
int temp = 0;
int val = 0;
for(int j = 0;j < m;j = j + 1)
{
if(state & (1 << j))
val = val + price[j];
}
if(val <= p)
{
for(int i = 0;i < n;i = i + 1)
{
int flag = 1;
for(int j = 0;j < m;j = j + 1)
{
if((need[i] & state) != need[i])
{
flag = 0;
break;
}
}
temp = temp + flag;
}
ans = max(ans,temp);
}
}
cout << ans << endl;
}
}