P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy Holsteins

题目描述

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

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

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

输入格式

第一行一个整数 v，表示需要的维他命的种类数。
第二行 v 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 g，表示可用来喂牛的饲料的种数。
下面 g 行，第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。

输出格式

输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

输入输出样例

输入 #1复制

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399

输出 #1复制

2 1 3

说明/提示

【数据范围】
对于 100% 的数据，1≤v≤25，1≤g≤15。
输入的所有整数在 [1,1000] 范围内。

#include<bits/stdc++.h>
using namespace std;
const int N = 30,M = 20;
int val[N];//记录牛每天需要的每种维他命的最小量
int ans = 1e9;//存放最少需要多少种饲料
int cnt[M];//存放最优解 使用的是那种饲料
int st[M];//存放当前选了那种饲料
int g[M][N];//存放饲料的种类和每种饲料包含维他命的量
int n,m;bool check(int x){//遍历每一头牛是否都能满足for(int i = 1;i<=n;i++){int sum = 0;//记录所选饲料的种类能否满足当前这头牛所需要的最小维他命量for(int j = 1;j<=x;j++){ //选了x种饲料  st[j]存放的是那种饲料sum+=g[st[j]][i];}if(sum < val[i])  return false; //如果无法满足当前这头牛这该方案不合法}return true; //当前方案可以满足所有牛的需求
}
//u表示当前枚举到那种饲料,s表示饲料种类的个数
void dfs(int u,int s){if(u > m){if(check(s) && s < ans){ //如果当前方案可以满足所有的牛需要的维他命最小量 并且种类数量小于当前的种类数量ans = s;for(int i = 1;i<=s;i++){ // 记录所选的方案cnt[i] = st[i];}}return ;}st[s+1] = u;  //选这种饲料dfs(u+1,s+1);st[s+1] = 0;  //不选这种饲料dfs(u+1,s);
}int main(){cin>>n;for(int i = 1;i<=n;i++) cin>>val[i];cin>>m;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++)cin>>g[i][j];}dfs(1,0);cout<<ans<<" ";for(int i = 1;i<=ans;i++) cout<<cnt[i]<<" ";return 0;
}