疯狂折扣 - 购物策略算法挑战

题目背景

轰轰一家子听说，超市进行大打折，听说能'打成骨折'哦。那天晚上他们全家人都去了……。

题目描述

每人均可以购买每种商品，但这个商品只允许购买 1 个。

每人在他能够拎得动的重量之内，可以拿很多商品(即不超过他最大能拿的商品总重量)。

现在给出商品的价格与重量的信息表，并给出每个人能拿的商品总重量，求这一家人购买商品的最大总价值。

输入格式

数据具有多组数据。

第一行一个整数 T，共有 T 个数据。

接下来 T 组数据，

第一行一个正整数 N，表示疯狂折扣的商品个数。

随后 N 行给出两个整数 p_i，w_i，代表第 i 个商品的价格与重量。

随后一行一个整数 g，代表这一家子总人数。

再 g 行给出一个整数 g_i，代表第 i 个人能拿的最大商品总重量。

输出格式

对于每组数据，输出一行一个整数，代表这一家人购买商品的最大总价值。

样例 #1

样例输入 #1

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

样例输出 #1

72
514

提示

样例一说明

共 2 组数据求。

第 1 组，3 个商品，价格(单位: p)与重量(单位: w)是:

72p 17w
44p 23w
31p 24w

这一家人只有 1 人去了，他最重能拿 26w，只能选择第一个商品是最大价值 72。

数据规模与约定

题目数据组：1 ≤ T ≤ 1000,
疯狂折扣商品数：0 ≤ N ≤ 1000,
每件商品价格：1 ≤ p_i ≤ 100,
每件商品重量：1 ≤ w_i ≤ 30,
这家人数量：1 ≤ g ≤ 100,
每个人最大能拿的商品总重量：1 ≤ g_i ≤ 30
c++ co de.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,T;
int wi[1001],pi[1001],f[1001];
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>pi[i]>>wi[i];
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++){
            for(int j=30;j>=wi[i];j--){
                f[j]=max(f[j],f[j-wi[i]]+pi[i]);
            }
        }
        int g,sum=0;
        cin>>g;
        while(g--){
            int k;
            cin>>k;
            sum+=f[k];
        }
        cout<<sum<<endl;
    }
    return 0;
}