c++ 一维

#include <bits/stdc++.h>
using namespace std;

const int N=105;
int n,m;
int v[N][N], w[N][N], s[N];
int f[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]);

    cout<<f[m]<<endl;
    return 0;
}

c++ 二维

#include <bits/stdc++.h>
using namespace std;

const int N=105;

int f[N][N], g[N];
int v[N][N], w[N][N], s[N];
int n,m;

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

    // 物品-体积-决策三重循环
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=m; ++j){
            for(int k=1; k<=s[i]; ++k){
                f[i][j]=max(f[i-1][j], f[i][j]); // 考虑改组可以不选择物品, 因此需要和f[i-1][j]进行一次比较
                if(j>=v[i][k]) f[i][j]=max(f[i][j], f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }

    cout<<f[n][m]<<endl;
    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, m:int, v:List[List[int]], w:List[List[int]], s:List[int]):
        f=[0 for _ in range(m+1)]
        for i in range(n):
            for j in range(m+1)[::-1]:
                for k in range(s[i]):
                    if j>=v[i][k]: f[j]=max(f[j], f[j-v[i][k]]+w[i][k])
        print(f[m])


if __name__ == '__main__':
    v, w, s=[], [], []
    n, m = map(int, input().split())
    for i in range(n):
        s.append(int(input()))
        v.append([])
        w.append([])
        for _ in range(s[i]):
            _v, _w = map(int, input().split())
            v[i].append(_v)
            w[i].append(_w)

    sol =Solution()
    sol.main(n, m, v, w, s)