Posted on 2009-03-26 18:20
superman 阅读(79)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m;
6 int need[25];
7 int feed[15][25];
8
9 int ans = 32767;
10 int cur_need[25], x[15], bestx[15];
11
12 void search(int i, int c)
13 {
14 if (i == m)
15 {
16 int j;
17 for (j = 0; j < n; j++)
18 if (cur_need[j] < need[j])
19 break;
20 if (j == n)
21 {
22 ans = c;
23 memcpy(bestx, x, sizeof(x));
24 }
25 return;
26 }
27
28 if (c + 1 < ans)
29 {
30 for (int j = 0; j < n; j++)
31 cur_need[j] += feed[i][j];
32 x[i] = 1;
33
34 search(i + 1, c + 1);
35
36 x[i] = 0;
37 for (int j = 0; j < n; j++)
38 cur_need[j] -= feed[i][j];
39 }
40
41 search(i + 1, c);
42 }
43
44 int main()
45 {
46 freopen("holstein.in", "r", stdin);
47 freopen("holstein.out", "w", stdout);
48
49 cin >> n;
50 for (int i = 0; i < n; i++)
51 cin >> need[i];
52 cin >> m;
53 for (int i = 0; i < m; i++)
54 for (int j = 0; j < n; j++)
55 cin >> feed[i][j];
56
57 search(0, 0);
58
59 cout << ans << ' ';
60 for (int i = 0, j = 0; j < ans; i++)
61 if (bestx[i])
62 {
63 j++;
64 cout << i + 1 << (j == ans ? '\n' : ' ');
65 }
66
67 return 0;
68 }
69