题目如下： 农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持他们的健康,使喂给牛的饲料的种数最少。给出牛所需的最低的维他命,输出喂给牛需要哪些种类的饲料? 给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。 维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。 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
这一道题第一眼看起来认为书是动态规划，其实一个dfs就可以解决 代码如下：
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> using namespace std; int a[26][26],b[26]; int bj[26],js=2147483,ko=1,n,m; char s[100],l[100]; int pd() { for(int i=1; i<=n; i++) if(bj[i]<b[i])//判断是不是维生素大于牛所需的最低的维他命 return 0;//如果不是返回0 return 1;//如果是返回1 } void dfs(int k,int ans) { if(pd()==1) {//如果 维生素大于牛所需的最低的维他命 if(js>ans) {//如果当前最小值大于本次的值 for(int i=1; i<=m; i++) l[i]=s[i];//把s数组的值赋给l数组 } js=min(js,ans);//取js和ans中的最小值 return ;//返回 } for(int i=k+1; i<=m; i++) { for(int j=1; j<=n; j++) bj[j]+=a[i][j]; s[i]='1';//表记i说明i点别被选过 dfs(i,ans+1);//搜索 for(int j=1; j<=n; j++) bj[j]=bj[j]-a[i][j]; s[i]='0';//讲i的表记清空 } } int main() { cin>>n;//输入 for(int i=1; i<=n; i++) cin>>b[i]; cin>>m; for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) cin>>a[i][j]; for(int ii=1; ii<=m; ii++) { memset(s,0,sizeof(s));//把s数组的值清空 s[ii]='1';//表记ii memset(bj,0,sizeof(bj));//把bj数组清空 for(int j=1; j<=n; j++) bj[j]=a[ii][j]; dfs(ii,1);//搜索 } cout<<js<<" "; for(int i=1; i<=m; i++) { if(l[i]=='1')//如果点i被标记过 cout<<i<<" ";//输出 } return 0; }