题目大意：
知道每种饲料中所包含的维他命量和牛所需的最低的维他命量。输出喂给牛需要哪些种类的饲料，且所需的饲料种类最少。
思路：
按照饲料种类进行深搜，对每种饲料只考虑使用或不使用。
代码：
/*
ID: lujunda1
LANG: C++
PROG: holstein
*/
#include
#include
using namespace std;
int V,G,v[25],g[15][25],total;
//total表示最优方案所选择的饲料的数量。
bool mark[25];
//对选择的饲料进行标记。
void input()
//输入
{
scanf("%d",&V);
for(int i=0;i<V;i++)
{
scanf("%d",&v[i]);
mark[i]=true;
//默认选择全部饲料。
}
scanf("%d",&G);
for(int i=0;i<G;i++)
for(int j=0;j<V;j++)
scanf("%d",&g[i][j]);
total=G;
//默认选择全部饲料。
}
void output()
//输出结果
{
printf("%d",total);
for(int i=0,j=0;j!=total;i++)
//输出前total个被标记的饲料。
if(mark[i])
{
printf(" %d",i+1);
j++;
}
printf("\n");
}
void updata(int n,int t)
//根据选择或除去第n个饲料来更新v[]。
//选择或除去由参数t决定。
{
for(int i=0;i<V;i++)
v[i]+=g[n][i]*t;
}
bool check()
//检查v[]的所有元素是否都不大于0。
{
for(int i=0;i0)
return false;
return true;
}
bool dfs(int n,int s)
//按饲料种类进行深搜。
//参数n表示第n个饲料。
//参数s表示已选择的饲料数量。
{
if(s==total)
//若选择的饲料数量不小于已有最优方案的选择数量。
return false;
if(check())
//若有更优方案。
{
total=s;
return true;
}
if(n==G)
//若已没有更多饲料可供选择。
return false;
bool check_temp=false;
updata(n,-1);
//使用当前饲料。
if(dfs(n+1,s+1))
{
check_temp=true;
mark[n]=true;
//对第n个饲料进行标记。
}
updata(n,1);
//不使用当前饲料。
if(dfs(n+1,s))
{
check_temp=true;
mark[n]=false;
//取消第n个饲料的标记。
}
return check_temp;
}
int main()
{
freopen("holstein.in","r",stdin);
freopen("holstein.out","w",stdout);
input();
dfs(0,0);
output();
}