状态压缩，先将生成的所有状态排序，然后枚举即可。
/* PROG : holstein LANG : C */ # include <stdio.h> # include <stdlib.h> struct scoop{int a[30];}; int V, G, r[(1 << 17) + 5]; struct scoop g[17], v; /***************************************************/ int bcnt(int x) { int ret = 0; while (x) { ++ret; x &= x-1; } return ret; } int cmp(const void *xx, const void *yy) { int x = *(int*)xx; int y = *(int*)yy; int t = bcnt(x) - bcnt(y); if (t == 0) return x>y ? 1:-1; return t; } void pre(void) { int i; for (i = 0; i < (1<<(G+1)); ++i) r[i] = i; qsort(r, (1<<(G+1)), sizeof(r[1]), cmp); } int cal(int x) { int i, j; struct scoop tmp = v; for (i = 0; i < G; ++i) if ((x>>i) & 0x1) for (j = 1; j <= V; ++j) tmp.a[j] -= g[i+1].a[j]; for (j = 1; j <= V; ++j) if (tmp.a[j] > 0) return 0; return 1; } void solve(void) { int i, k; pre(); for (i = 0; i < (1<<(G+1)); ++i) if (cal(r[i])) break; printf("%d", bcnt(r[i])); for (k = 0; k < G; ++k) if ((r[i]>>k)&0x1) printf(" %d", k+1); putchar('\n'); } /***************************************************/ void read(void) { int i, j; scanf("%d", &V); for (i = 1; i <= V; ++i) scanf("%d", &v.a[i]); scanf("%d", &G); for (i = 1; i <= G; ++i) for (j = 1; j <= V; ++j) scanf("%d", &g[i].a[j]); } int main() { freopen("holstein.in", "r", stdin); freopen("holstein.out", "w", stdout); read(); solve(); fclose(stdin); fclose(stdout); return 0; }
DFS 毫无疑问会超时。