這題想通了很簡單，不過難的就是想的過程，我想了一個上午，由于沒有去重超時了，后來還是同學點撥才過的，用數組模擬組合，當數組的某個元素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