xinjun与阴阳师 -分组背包

关于分组背包传送门

code

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 5;

int dp[maxn],val[maxn][maxn],w[maxn][maxn];
int num[maxn];

void Solve(int n,int m)
{
    memset(dp, 0, sizeof dp);
    for(int i = 1; i <= n; i++){
        cin>>num[i];
        for(int j = 1; j <= num[i]; j++) cin>>val[i][j];
        for(int j = 1; j <= num[i]; j++) cin>>w[i][j];
    }
    for(int i = 1; i <= n; i++){
        for(int j = m; j >= 0; j--){
            for(int k = 1; k <= num[i]; k++){
                if(j >= w[i][k]) dp[j] = max(dp[j],dp[j - w[i][k]] + val[i][k]);
            }
        }
    }
    cout<<dp[m]<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        Solve(n,m);
    }
    return 0;
}