记住体积倒序,因为每组只能取一个
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> #include<string> using namespace std; int dp[110], v[110], w[110]; int n, m, s; int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> s; for(int j = 1; j <= s; j++) cin >> v[j] >> w[j]; for(int j = m; j >= 0; j--) for(int k = 1; k <= s; k++) if(j >= v[k]) dp[j] = max(dp[j], dp[j-v[k]]+w[k]); } cout << dp[m]; return 0; }