题目描述

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

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

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

思路

暴力搜索每一个点，选或不选，如果当前个数比最小个数要小就搜下去，不然就退出
O(2^m)

/*
ID: a1192631
PROG: holstein
LANG: C++
*/
#include <stdio.h>
int a[26][26];
int f[26],fl[26],ll[26];
int n,m,ans=0,min=1000;
int dfs(int dep)
{
    if (dep>m) return 0;
    int t=0;
    for (int i=1;i<=n;i++)
    {
        f[i]-=a[dep][i];
        if (f[i]<=0) t++;
    }
    fl[dep]=1; ans++;
    if (t==n)
    {
        for (int i=1;i<=m;i++)
            ll[i]=fl[i];
        min=ans;
    }
    if (ans+1<min)
        dfs(dep+1); 
    fl[dep]=0; ans--;
    for (int i=1;i<=n;i++)
    {
        f[i]+=a[dep][i];
    }
    dfs(dep+1);
}
int main()
{
     freopen("holstein.in", "r", stdin);
    freopen("holstein.out", "w", stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&f[i]);
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    dfs(1);
    printf("%d",min);
    for (int i=1;i<=m;i++)
        if (ll[i]==1) printf(" %d",i);
    printf("\n");
}