/**//*
ID: lorelei3
TASK: holstein
LANG: C++
*/
#include <fstream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
const int MAX = 30;
int V, G; // V 需要维他命种类数, G可以喂牛的饲料种数
int need[MAX];
int kind[MAX][MAX];
int x[MAX];
int best[MAX];
int y[MAX];
int total=100000000 , num = MAX;
bool check()
{
int i,j, times=0,to=0;
memset(y, 0, sizeof(y));
for(i=0; i<G; ++i){
if(x[i]){
times++;
for(j=0; j<V; ++j)
y[j] += kind[i][j];
}
}
for(i=0; i<V; ++i){
if(y[i]<need[i])
return false;
else
to +=y[i];
}
if(times<num){
if(to<total){
total = to;
return true;
}
else
return false;
}else
return false;
}
void dfs(int t){
if(t>=G){
if(check()){
num = 0;
for(int i=0; i<G; ++i){ best[i] = x[i]; num+=best[i]; }
}
}else
for(int i=0 ; i<=1; ++i){
x[t] = i;
dfs(t+1);
}
}
int main(){
int i,j;
ifstream in("holstein.in");
ofstream out("holstein.out");
in>>V;
for(i=0; i<V; ++i)
in>>need[i];
in>>G;
for(i=0; i<G; ++i)
for(j=0; j<V; ++j)
in>>kind[i][j];
dfs(0);
char* ch=" ";
out<<num<<ch;
for(i=0,j=0; i<G; ++i){
if(best[i]){
j++;
if(j==num) ch="";
out<<i+1<<ch;
}
}
out<<endl;
return 0;
}
posted on 2010-11-21 00:46
小阮 阅读(166)
评论(0) 编辑 收藏 引用 所属分类:
USACO