题目描述

自己读题去

C++ 代码

#include <bits/stdc++.h>
const int maxn = 105;
const int inf = 0x3f3f3f3f;
typedef long long LL;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) +(s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

int N;
int V;
int s[maxn];
int w[maxn][maxn];
int v[maxn][maxn];
int f[maxn];

int main() {
    read(N), read(V);
    for (int i = 1; i <= N; ++i) {
        read(s[i]);
        for (int j = 1; j <= s[i]; ++j) {
            read(w[i][j]);
            read(v[i][j]);
        }
    }

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

    printf("%d\n", f[V]);
    return 0;
}