$题面是中文版$题面是中文版

分析

个人认为这题非常考验对背包的理解！
我尝试把这道题讲清楚吧。
首先见到这题第一感觉就是NOIP2006金明的预算方案。把每一个主件的所有组合记录下来，然后进行分组背包，代码如下：

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int f[N], cnt[55], w[55][1050], v[55][1050], p[11], q[11];
int main(){
    int i, j, k, n, m, a, b, s1, s2;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++){
        scanf("%d%d", &a, &b);
        for(j = 0; j < b; j++) scanf("%d%d", &p[j], &q[j]);
        for(j = 0; j < (1 << b); j++){
            s1 = s2 = 0;
            for(k = 0; k < b; k++){
                if((1 << k) & j) s1 += p[k], s2 += q[k];
            }
            if(a + s1 > m) continue;
            cnt[i]++;
            w[i][cnt[i]] = a + s1;
            v[i][cnt[i]] = s2;
        }
    }
    for(i = 1; i <= n; i++){
        for(j = m; j >= 0; j--){
            for(k = 1; k <= cnt[i]; k++){
                if(j >= w[i][k]) f[j] = max(f[j], f[j - w[i][k]] + v[i][k]);
            }
        }
    }
    printf("%d", f[m]);
    return 0;
}

但是这是tle的！！！！

因为每个主件的组合数是 $2^b$2b 个，最坏情况下复杂度高达 $O(2^b\ast N\ast V)$O(2b∗N∗V)。但是这种做法明明很正确呀，每种组合确实都需要考虑到。但这题复杂度要求的明显是 $O(N\ast V)$O(N∗V)，怪了！
且慢，先让我们回忆一下经典的 $0/1$0/1背包问题。
初学者遇到 $0/1$0/1背包问题，想的可能是枚举所有组合，然后取最大价值，复杂度是 $O\left(2^n\right)$O(2n)。但是我们的做法是用dp， $f\left[i\right]\left[j\right]=max\left(f\right[i-1\left]\right[j],f[i-1\left]\right[j-w]+v)$f[i][j]=max(f[i−1][j],f[i−1][j−w]+v)，每一件物品是否算入也是考虑到了的。问题在于，对每一件物品，我们只考虑了一次，相当于定序了，而初学者考虑了 $2^{n-1}$2n−1 次， 相当于无序的，而这个东西放不放和其他东西放不放是没有关系的。
回到这题，我们是不是也可以把 $2^b$2b 部分给搞掉呢？答案是显然的。
转移方程如下：
$f\left[i\right]\left[j\right]=max\left(f\right[i\left]\right[j],f[i\left]\right[j-w]+v)$f[i][j]=max(f[i][j],f[i][j−w]+v)
为什么不是 $f[i-1][j-w]$f[i−1][j−w]？因为这是个多重背包问题啊，我们相当于是在每一个主件下面进行了一次 $0/1$0/1背包，每个附件可取可不取，相当于是子问题吧！于是我们的整体做法就出来了：
枚举主件，因为要选的话主件一定要选，所以是个 $1/1$1/1背包（神特么1/1背包）。然后对附件进行 $0/1$0/1背包，最后再考虑整一套不选的情况就可以了。

代码如下（很是简洁呢）

#include <bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
int f[55][N], ans;
int main(){
	int i, j, k, n, m, a, b, w, v;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		scanf("%d%d", &a, &b);
		for(j = m; j >= a; j--) f[i][j] = f[i-1][j-a];
		for(j = 1; j <= b; j++){
			scanf("%d%d", &w, &v);
			for(k = m; k >= w + a; k--){
				f[i][k] = max(f[i][k], f[i][k-w] + v);
			}
		}
		for(j = 0; j <= m; j++) f[i][j] = max(f[i][j], f[i-1][j]);
	}
	printf("%d", f[n][m]);
	return 0;
}