由于(1≤v≤25,1le g le 15),数据范围比较小,所以可以枚举出所有饲料的选择情况((2^{15} = 32768)),再取其中字典序最小的,饲料种数最少的方案
#include<iostream>
#include<vector>
using namespace std;
const int N = 25;
vector<int> res, backup;
vector<int> a;
vector<vector<int>> b;
int v, g;
void dfs(int u){
if(u == g){
// 是否满足奶牛的需要、比较一下字典序、比较一下饲料的个数
bool flag = 1;
for(int i = 0; i < v; i ++){
int sum = 0;
for(int j = 0; j < backup.size(); j ++)
sum += b[backup[j]][i];
if(sum < a[i]) flag = 0;
}
if(flag){
if(res.size() == 0 || res.size() > backup.size())
res = backup;
else if(res.size() == backup.size())
if(res[0] > backup[0]) res = backup;
}
return;
}
dfs(u + 1);
backup.push_back(u);
dfs(u + 1);
backup.pop_back();
}
int main(){
cin >> v;
for(int i = 0; i < v; i ++){
int t;
cin >> t;
a.push_back(t);
}
cin >> g;
for(int i = 0; i < g; i ++){
vector<int> c;
for(int j = 0; j < v; j ++){
int t;
cin >> t;
c.push_back(t);
}
b.push_back(c);
}
dfs(0);
cout << res.size() << ' ';
for(auto t : res) cout << t + 1 << ' ';
return 0;
}