1023. 【USACO题库】2.1.4 Healthy Holsteins健康的好斯坦奶牛

输出文件名(Input: holstein.in, Output: holstein.out)

时间限制: 1 s 空间限制: 256 MB

题目描述 :

农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持他们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命，输出喂给牛需要哪些种类的饲料，且所需的种类数最少。

输入 :

从文件holstein.in中读入数据。

第1行：一个整数V(1<=V<=25)，表示需要的维他命的种类数。

第2行：V个整数(1<=每个数<=1000)，表示牛每天需要的维他命的最小量。

第3行：一个整数G(1<=G<=15)，表示可用来喂牛的饲料的数量。下面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，所以我们可以枚举所有饲料组合（子集），检查是否满足维生素需求，找到包含饲料数最少的那一组。

步骤：

1. 读入 V、维生素需求数组、G、每种饲料的维生素含量。

2. 使用 DFS（深度优先搜索）枚举所有子集，也可用二进制枚举。

3. 每次枚举到一个组合时，计算各种维生素的总量。

4. 判断是否满足所有维生素的最低需求。

5. 若满足且饲料数量小于当前最优解，则更新最优方案。

6. 输出最优方案的种数及编号（编号从 1 开始）。

代码：

#include<bits/stdc++.h> using namespace std; int N,M; int v[30]; int vv[1010][1010]; int vis[30]; int temp[25]; int rst=25; int isok(int *A,int cur) { int i,j,sum; for (i=0;i<N;i++) { sum=0; for(j=0;j<cur;j++) sum=sum+vv[A[j]][i]; if(sum<v[i]) return 0; } return 1; } void print_subset(int n,int* A,int cur) { int i; if(isok(A,cur)&&cur<rst) { rst=cur; for(i=0;i<cur+1;i++) { vis[i]=A[i]; } } int s=cur?A[cur-1]+1:0; for(i=s;i<n;i++) { A[cur]=i; print_subset(n,A,cur+1); } } int main() { freopen("holstein.in","r",stdin); freopen("holstein.out","w",stdout); cin>>N; int i,j; for (i=0;i<N;i++) cin>>v[i]; cin>>M; for (i=0;i<M;i++) for(j=0;j<N;j++) cin>>vv[i][j]; print_subset(M,temp,0); cout<<rst; for(i=0;i<rst;i++) cout<<" "<<(vis[i]+1); cout<<endl; return 0; }

运行语言：C++11。