空间优化版:由于只使用到当前层和上一层

C++ 代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 110;
int main(){
    int n,m,s,v,w;
    cin>>n>>m;
    vector<int> f(N,0); 
    for(int i = 1; i <= n; i++){
        cin>>s;
        vector<int> ff(f.begin(),f.end());
        for(int j= 1; j <= s; j++ ){
            cin>>v>>w;
            for(int k = m; k >= v; k--){
               f[k] = max(f[k],ff[k-v]+w);
            }
        }
    }
    cout<<f[m];
    return 0;
}