输出文件名(Input: holstein.in, Output: holstein.out)时间限制: 1 s 空间限制: 256 MB题目描述 :农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛以保持他们的健康使喂给牛的饲料的种数最少。给出牛所需的最低的维他命输出喂给牛需要哪些种类的饲料且所需的种类数最少。输入 :从文件holstein.in中读入数据。第1行一个整数V(1V25)表示需要的维他命的种类数。第2行V个整数(1每个数1000)表示牛每天需要的维他命的最小量。第3行一个整数G(1G15)表示可用来喂牛的饲料的数量。下面G行第i行表示编号为i饲料包含的各种维他命的量的多少。输出 :输出到文件holstein.out中。输出文件只有一行包括牛必需的最小的饲料种数P后面有P个数表示所选择的饲料编号按从小到大排列。样例输入 :4 100 200 300 400 3 50 50 50 50 200 300 200 300 900 150 389 399样例输出 :2 1 3解题思路因为 G 最大只有 15所以我们可以枚举所有饲料组合子集检查是否满足维生素需求找到包含饲料数最少的那一组。步骤读入 V、维生素需求数组、G、每种饲料的维生素含量。使用 DFS深度优先搜索枚举所有子集也可用二进制枚举。每次枚举到一个组合时计算各种维生素的总量。判断是否满足所有维生素的最低需求。若满足且饲料数量小于当前最优解则更新最优方案。输出最优方案的种数及编号编号从 1 开始。代码#includebits/stdc.h using namespace std; int N,M; int v[30]; int vv[1010][1010]; int vis[30]; int temp[25]; int rst25; int isok(int *A,int cur) { int i,j,sum; for (i0;iN;i) { sum0; for(j0;jcur;j) sumsumvv[A[j]][i]; if(sumv[i]) return 0; } return 1; } void print_subset(int n,int* A,int cur) { int i; if(isok(A,cur)currst) { rstcur; for(i0;icur1;i) { vis[i]A[i]; } } int scur?A[cur-1]1:0; for(is;in;i) { A[cur]i; print_subset(n,A,cur1); } } int main() { freopen(holstein.in,r,stdin); freopen(holstein.out,w,stdout); cinN; int i,j; for (i0;iN;i) cinv[i]; cinM; for (i0;iM;i) for(j0;jN;j) cinvv[i][j]; print_subset(M,temp,0); coutrst; for(i0;irst;i) cout (vis[i]1); coutendl; return 0; }运行语言C11。