hdu 3033 I love sneakers!（分组背包：每组至少一个）
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 890????Accepted Submission(s): 381
?
#include <iostream>#include <stdio.h>#include <memory.h>using namespace std;const int INF = 99999999;int max(int a, int b, int c){ int M; M = a > b ? a : b; M = M > c ? M : c; return M;}int c[105], w[105], s[105];int bag[15][10005];int N, V, S;void _gro_bag(){ int i, j, k; for(i = 1; i <= S; i++) for(j = 0; j <= V; j++) bag[i][j] = -INF; for(i = 1; i <= S; i++) for(k = 0; k < N; k++) for(j = V; j >= 0; j--) if(s[k] == i && j >= c[k]) bag[i][j] = max(bag[i][j], bag[i-1][j-c[k]]+w[k], bag[i][j-c[k]]+w[k]);}int main(){ int i; while(scanf("%d %d %d", &N, &V, &S) != EOF) { for(i = 0; i < N; i++) scanf("%d%d%d", &s[i], &c[i], &w[i]); _gro_bag(); if(bag[S][V] < 0) printf("Impossible\n"); else printf("%d\n", bag[S][V]); } return 0;}?
