Input Specification
The input consists of T test cases. The number of them (1<=T<=1000) is given on the first line of the input file.
Each test case begins with a line containing a single integer number N that indicates the number of objects (1 <= N <= 1000). Then follows Nlines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The second integer (1<=W<=30) corresponds to the weight of object. Next line contains one integer (1<=G<=100) it’s the number of people in our group. Next G lines contains maximal weight (1<=MW<=30) that can stand this i-th person from our family (1<=i<=G).
Output Specification
For every test case your program has to determine one integer. Print out the maximal value of goods which we can buy with that family.
Sample Input
2
3
72 17
44 23
31 24
1
26
6
64 26
85 22
52 4
99 18
39 13
54 9
4
23
20
20
26
Output for the Sample Input
72
514
题意：有g个人去采购，每个人都有一定的负重量mw，有n样商品，每个商品都有价值p和重量w。要求所有人采购，
每个人每样商品只能采购一次，要求最后所有人采购的总价值最大。
思路：01背包问题。状态转移方程为dp[j] = max(dp[j - w[i]] + p[i], dp[j])。
代码：
#include#include int t, n, p[1005], w[1005], g, mw, i, j, dp[30005], sum; int max(int a, int b) { return a > b a : b; } int main() { scanf("%d", &t); while (t --) { sum = 0; int s = 0; scanf("%d", &n); for (i = 0; i < n; i ++) { scanf("%d%d", &p[i], &w[i]); s += w[i]; } memset(dp, 0, sizeof(dp)); for (i = 0; i < n; i ++) for (j = s; j >= w[i]; j --) { if (dp[j - w[i]] || j - w[i] == 0) dp[j] = max(dp[j - w[i]] + p[i], dp[j]); } scanf("%d", &g); while (g --) { int Max = 0; scanf("%d", &mw); for (i = 0; i <= mw; i ++) Max = max(Max, dp[i]); sum += Max; } printf("%d\n", sum); } return 0; }