分组背包

类似多重背包，只是将每件物品选几个变成每组物品选哪一个

状态转移方程 f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] ) f[i][j] = Max(f[i-1][j],f[i-1][j-v[i][k]] + w[i][k]) f[i][j]=Max(f[i−1][j],f[i−1][j−v[i][k]]+w[i][k])

所以优化成一维时需要从大到小枚举 j j j

int n, m;
int f[N];
int v[N][N], w[N][N], s[N];
int main() {
   
	cin >> n >> m;
	for (int i = 1;i <= n;++i) {
   
		cin >> s[i];
		for (int j = 0;j < s[i];++j) {
   
			cin >> v[i][j] >> w[i][j];
		}
	}

	for (int i = 1;i <= n;++i) {
   
		for (int j = m;j >= 0;--j) {
   
			for (int k = 0;k < s[i];++k) {
   
				if (v[i][k] <= j)f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
			}
		}
	}