这题想通了很简单，不过难的就是想的过程，我想了一个上午，由于没有去重超时了，后来还是同学点拨才过的，用数组模拟组合，当数组的某个元素a[i]=1时表示选取第(i-1)(或者i，这里看数组的下标从0开始还是从1开始)个，a[i] = 0表示不选第(i-1)个。然后再在符合情况的组合中选取元素最少的(也就是步数最少的)。
官方的报告和这一样的思路
官方
1
Since there are only 15 feeds, and for each feed we can either give zero or one scopes of it, there are 215 possible `feed mixtures' the cows can be fed, which is only 32,768. Therefore, try all combinations and pick which of the legal combinations uses the least number of feeds.
2
3#include <stdio.h>
4#include <assert.h>
5
6#define MAXV 25
7#define MAXF 15
8
9int req[MAXV]; /**//* the vitamin requirements */
10int numv; /**//* number of vitamins */
11
12int feeds[MAXF][MAXV]; /**//* the vitamin within each feed */
13int numf; /**//* number of feeds */
14
15int best; /**//* the minimum number of feeds to use found thus far */
16int bestf[MAXF]; /**//* the set */
17
18int curf[MAXF]; /**//* the current set of feeds being considered */
19
20void find_feed(int fcnt, int fid)
21 
{ /**//* fcnt is the number of feeds in the current mixture,
22
fid is the identifier of the first feed to try adding (last feed + 1) */
23
int lv;
24
25
/**//* check if the requirement has been met */
26 for (lv = 0; lv < numv; lv++)
27 if (req[lv] > 0) break;
28 if (lv >= numv)
29 { /**//* all the requirements are met */
30 /**//* we know this is better, since we wouldn't have checked it otherwise
31 (see below) */
32 best = fcnt;
33 for (lv = 0; lv < best; lv++)
34 bestf[lv] = curf[lv];
35 return;
36 }
37
38 while (fid < numf && fcnt+1 < best)
39 { /**//* try adding each feed to the mixture */
40 /**//* the fcnt+1 < best ensures that we stop if there's no hope
41 in finding a better solution than one found already */
42
43 /**//* add the vitamins from this feed */
44 for (lv = 0; lv < numv; lv++)
45 req[lv] -= feeds[fid][lv];
46 curf[fcnt] = fid; /**//* put it in the list */
47
48 find_feed(fcnt+1, fid+1);
49
50 /**//* undo adding the vitamins */
51 for (lv = 0; lv < numv; lv++)
52 req[lv] += feeds[fid][lv];
53
54 /**//* next feed */
55 fid++;
56 }
57
}
58
59int main(void)
60 {
61 FILE *fin, *fout;
62 int lv, lv2;
63
64 fin = fopen("holstein.in", "r");
65 fout = fopen("holstein.out", "w");
66 assert(fin);
67 assert(fout);
68
69 fscanf (fin, "%d", &numv);
70 for (lv = 0; lv < numv; lv++)
71 fscanf (fin, "%d", &req[lv]);
72 fscanf (fin, "%d", &numf);
73 for (lv = 0; lv < numf; lv++)
74 for (lv2 = 0; lv2 < numv; lv2++)
75 fscanf (fin, "%d", &feeds[lv][lv2]);
76
77 best = numf+1;
78 find_feed(0, 0);
79
80 fprintf (fout, "%i", best);
81 for (lv = 0; lv < best; lv++)
82 fprintf (fout, " %i", bestf[lv]+1);
83 fprintf (fout, "\n");
84 return 0;
85 }
86
87