健康的好斯坦奶牛
农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持他们的健康，使喂给牛的饲料的种数最少。
给出牛所需的最低的维他命，输出喂给牛需要哪些种类的饲料。
PROGRAM NAME: holstein
INPUT FORMAT
第1行：一个整数V(1<=V<=25)，表示需要的维他命的种类数。
第2行：V个整数(1<=每个数<=1000)，表示牛每天需要的维他命的最小量。
第3行：一个整数G(1<=G<=15)，表示可用来喂牛的饲料的数量。下面G行，第i行表示编号为 i饲料包含的各种维他命的量的多少。
SAMPLE INPUT (file holstein.in)
4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399
OUTPUT FORMAT
输出文件只有一行，包括：
牛必需的最小的饲料种数P
后面有P个数，表示所选择的饲料编号（按从小到大排列）。
SAMPLE OUTPUT (file holstein.out)
2 1 3
分析：
没什么说的，经典的深搜题，搜索每种饲料用了没有，即每层搜索有两种状态：s[n]=0或s[n]=1。（第n层表示搜索到了第n种饲料），一个小剪枝：不必搜到n=G，只要搜到可供的维生素够用就可以退出（因为要求最少需要的饲料，再往后面走只会多不会少）
代码：
/*
ID: 138_3531
LANG: C++
TASK: holstein
*/
#include<fstream>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
ifstream fin("holstein.in");
ofstream fout("holstein.out");
int N;
int v[25]; //每种维生素所需
int G;
int f[15][25]; //第i种饲料能提供多少j维生素
int s[15]; //记录第i种饲料用没用
int p[25]; //每种维生素已经提供了多少
int minans;
int hash[15]; //记录每次搜索哪种饲料被用过
void input()
{
fin>>N;
for (int i=0;i<N;i++)
fin>>v[i];
fin>>G;
for (int i=0;i<G;i++)
for (int j=0;j<N;j++)
fin>>f[i][j];
}
void dfs(int n)
{
int ok=1; //深搜边界，带剪枝，一旦满足所有维生素便退出，不再多加饲料种类
for (int i=0;i<N;i++)
if (p[i]<v[i])
{
ok=0;
break;
}
if (ok)
{
int ans=0;
for (int i=0;i<n;i++)
ans+=s[i];
if (ans<=minans)
{
minans=ans;
memset(hash,0,sizeof(hash));
for (int i=0;i<G;i++)
if (s[i]==1) hash[i]=1;
}
return;
}
if (n==G) return;
for (s[n]=0;s[n]<=1;s[n]++)
{
for (int i=0;i<N;i++)
p[i]+=f[n][i]*s[n];
dfs(n+1);
for (int i=0;i<N;i++)
p[i]-=f[n][i]*s[n];
}
}
int main()
{
input();
minans=100000;
dfs(0);
fout<<minans;
for (int i=0;i<G;i++)
if (hash[i]) fout<<' '<<i+1;
fout<<endl;
return 0;
}