Consumer HDU

FJ打算去购物，在此之前，他需要一些盒子来装他要买的各种各样的东西。每个盒子都用来携带一些特定的东西(也就是说，如果他要买这些东西，他必须事先买到盒子)。每种东西都有自己的价值。现在FJ的购物金额只有W美元，他想用这笔钱购物,使他所买的物品的总价值最高。 
 有多组测试数据 

Input 每组数据的第一行两个整数，盒子的个数n (1 <= n <= 50)，FJ所携带钱的总额 w (1 <= w <= 100000) 
 接下来的n行中。每行前两个整数为：第i个盒子的价格pi(1<=pi<=1000)，这个盒子可携带的物品的数量 mi (1<=mi<=10)接下来有mi对数字，表示物品的价格cj (1<=cj<=100)，价值vj(1<=vj<=1000000)Output对于每一组测试数据，输出FJ可以得到价值的最大值 
Sample Input

3 800
300 2 30 50 25 80
600 1 50 130
400 3 40 70 30 40 35 60

Sample Output

210

code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int dp[maxn];
int tmp[maxn];

int main()
{
    int n, v;
    while (cin >> n >> v)
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
        {
            int p, num; cin >> p >> num;

            memcpy(tmp, dp, sizeof(dp));
            for (int j = 1; j <= num; j++)
            {
                int w, val;
                scanf("%d%d", &w, &val);
                for (int k = v - p; k >= w; k--)
                    tmp[k] = max(tmp[k], tmp[k - w] + val);
            }
            for (int j = 0; j <= v - p; j++)
                dp[j + p] = max(dp[j + p], tmp[j]);
        }
        cout << dp[v] << endl;
    }
}