USACO 2.1 - Healthy Holsteins | Jack Neus

USACO 2.1 – Healthy Holsteins | Jack Neus

Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for the cows. Help Farmer John feed his cows so they stay healthy while minimizing the number of scoops that a cow is fed.

Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements.

Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data.

http://www.cnblogs.com/liushang0419/archive/2012/06/08/2541426.html

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

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

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

格式

PROGRAM NAME: holstein

INPUT FORMAT:(file holstein.in)

第1行：一个整数V(1<=V<=25)，表示需要的维他命的种类数。

第2行：V个整数(1<=每个数<=1000)，表示牛每天需要的每种维他命的最小量。

第3行：一个整数G(1<=G<=15)，表示可用来喂牛的饲料的种数。

下面G行，第n行表示编号为n饲料包含的各种维他命的量的多少。

OUTPUT FORMAT:(file holstein.out)

输出文件只有一行，包括

牛必需的最小的饲料种数P

后面有P个数，表示所选择的饲料编号（按从小到大排列）。

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

SAMPLE INPUT

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

SAMPLE OUTPUT

2 1 3

分析：
这个题目是找一个最优方案，由于数据比较小，直接枚举是直接可以过掉的，但是在枚举的实现上有两种思路。
第一种是按照乘法原理的思路，一共15种药，每一种要么选择，要么不选择，所以一共枚举次数的计算表达式为 2^15 这么多种。
第二种是按照组合原理的思路，一共15种药物，我分15次逐层深入遍历，需要的枚举次数最多为 C（15,1）＋C（15,2）.。。。＋C（15,15）.其值和2^15是一样的。

这两种方法都能通过代码实现，而且很容易，但是在效率上有比较大的区别，打个比方，假设一共只有三种药物，
那么按照第一种思路，枚举顺序为 001,010,011,100,101,110,111 （0,代表不选择，1代表选择，比如001即表示，只选择第三种药物）
按照第二种思路 ，枚举序列为 1,2,3,12,13,23,123 （可以发现1,2,3,属于C（3,1）,12,13,23 属于C（3,2）,123则属于C（3,3））

如果说那种思路好的话，那么根据这道题目的具体情况，肯定是第二种要好，因为本题对输出上有要求“如果有多个解，输出饲料序号最小的（即字典序最小）。”，可以发现第二种是正好按照题目要求的顺序来的，第一种思路的输出虽然也是“字典序”，但是他不符合“药物总数”从小达到大的输出要求，比如011在100前面，但是011表示两种药物，100表示一种药物。

我的代码是第二种思路，逐层生成组合序列，虽然每一层用的是DFS，但是整体上有点BSF的特点，因为只要找到就输出。后面的曾就不用搜索了。

x. DFS

https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/holstein.java
http://acm.sdibt.edu.cn/blog/?p=1035

	public static void main(String[] args) throws IOException {
	Scanner sc = new Scanner(new File("holstein.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("holstein.out")));
	V = sc.nextInt();
	min = new int[V];
	for(int i = 0; i < V;i++)
	{
	min[i] = sc.nextInt();
	}
	G = sc.nextInt();
	scoop = new int[G][V];
	for(int i = 0; i < G;i++)
	{
	for(int j = 0; j < V;j++)
	{
	scoop[i][j]= sc.nextInt();
	}
	}
	best = null;
	bestC = Integer.MAX_VALUE;
	recur(0,new boolean[G],0,new int[V]);
	ArrayList<Integer> ans = new ArrayList<Integer>();
	for(int i = 0; i < G;i++)
	{
	if(best[i]) ans.add(i+1);
	}
	Collections.sort(ans);
	out.print(ans.size());
	for(int a: ans)
	out.print(" "+a);
	out.println();
	out.close();
	}
	static int[] min;
	static int[][] scoop;
	static int V,G;
	static boolean[] best;
	static int bestC;
	public static void recur(int at, boolean[] used,int count,int[] vit)
	{
	if(at == used.length)
	{
	for(int i = 0; i < V;i++)
	{
	if(vit[i] < min[i]) return;
	}
	if(better(count,used))
	{
	bestC = count;
	best = used.clone();
	}
	return;
	}
	recur(at+1,used,count,vit);
	for(int i = 0; i < V;i++){
	vit[i] += scoop[at][i];
	}
	used[at] = true;
	recur(at+1,used,count+1,vit);
	for(int i = 0; i < V;i++){
	vit[i] -= scoop[at][i];
	}
	used[at] = false;
	}
	public static boolean better(int count, boolean[] used)
	{
	if(count < bestC) return true;
	if(count > bestC) return false;
	for(int i = 0; i < G;i++)
	{
	if(used[i] && !best[i]) return true;
	if(!used[i] && best[i]) return false;
	}
	return false;
	}

http://lujunda.cn/2012/08/02/usacosection-2-1%E6%90%9C%E7%B4%A2-healthy-holsteins/

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;

}

X. 二进制枚举 http://simone-chou.iteye.com/blog/2015115
   直接用二进制枚举，0代表没选上，1代表选上。最多也就选择15种，故从从 1 枚举到pow（2，n）判断即可，加上剪枝。DFS会爆栈。

X. BFS
http://www.conlan.cc/2011/10/26/usaco-2-14-healthy-holsteins%EF%BC%88bfs/
Read full article from USACO 2.1 – Healthy Holsteins | Jack Neus