卢俊达

题目大意：

知道每种饲料中所包含的维他命量和牛所需的最低的维他命量。输出喂给牛需要哪些种类的饲料，且所需的饲料种类最少。

思路：

按照饲料种类进行深搜，对每种饲料只考虑使用或不使用。

代码：

/*
ID: lujunda1
LANG: C++
PROG: holstein
*/
#include<iostream>
#include<stdio.h>
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;i<V;i++)
		if(v[i]>0)
			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();
}