uva/10130.cpp at master · adnan0944/uva · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>


using namespace std;


int main()
{
    int t,cost[1005],weight[1005],weigh[105],dp[1002];

    int i, j, n, num, k, ans;
    scanf("%d", &t);
    while (t--)
    {
        ans = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
            scanf("%d %d", &cost[i],&weight[i]);
        scanf("%d", &num);
        for (i = 0; i < num; i++)
            scanf("%d", &weigh[i]);
        for (i = 0; i < num; i++)
        {
            memset(dp, 0, sizeof(dp));
            for (j = 0; j < n; j++)
                for (k = weigh[i]; k >= weight[j]; k--)
                    if (dp[k] < dp[k - weight[j]] + cost[j])
                        dp[k] = dp[k - weight[j]] + cost[j];
            ans += dp[weigh[i]];
        }
        printf("%d\n", ans);
    }
    return 0;

}