学步园

UVA_10130

    这个题目有好多背包，但由于物品是无限的，而每个人对任意一种物品只能取一个，所以本质上还是0-1背包问题。

#include<stdio.h>
#include<string.h>
#define MAXD 1010
#define MAXW 40
int N, M, G, f[MAXW], p[MAXD], w[MAXD], d[MAXW];
void init()
{
int i, j;
    scanf("%d", &N);
for(i = 0; i < N; i ++)
        scanf("%d%d", &p[i], &w[i]);
}
void solve()
{
int i, j, k, res = 0;
    scanf("%d", &G);
    memset(d, -1, sizeof(d));
for(i = 0; i < G; i ++)
    {
        scanf("%d", &M);
if(d[M] == -1)
        {
            memset(f, 0, sizeof(f));
for(j = 0; j < N; j ++)
for(k = M; k >= w[j]; k --)
if(f[k - w[j]] + p[j] > f[k])
                        f[k] = f[k - w[j]] + p[j];
            d[M] = f[M];
        }
        res += d[M];
    }
    printf("%d\n", res);
}
int main()
{
int t;
    scanf("%d", &t);
while(t --)
    {
        init();
        solve();
    }
return 0;
}