[USACO][Section 2.1][搜索] Healthy Holsteins

题目大意：

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

思路：

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

代码：

/*
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;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();
}