动态规划

#include "cstdio"
#include "iostream"
#include "algorithm"
#include "cstring"
using namespace std;
const int M=1e6+10;
struct node {
    int w[1010];
    int v[1010];
}s[1010];
int dp[M];
int main (){
     int t,n,m,k[1010];
     scanf ("%d",&t);
     while (t--){
         memset(dp,0,sizeof(dp));
         scanf ("%d%d",&n,&m);
             //一共有n个模式 
         for (int i = 1 ; i <= n ;i++){
             scanf ("%d",&k[i]);
             //输入副本所要消耗的体力，也就是物品的体积 
             for (int j = 1 ; j <= k[i];j++){
                 scanf ("%d",&s[i].v[j]);
             }
             //输入打完副本的价值，也就是物品的价值 
             for (int j = 1 ; j <= k[i];j++){
                 scanf ("%d",&s[i].w[j]);
             }
         }
         for(int i = 1 ; i <= n;i++){
             for (int q = m ; q >= 0;q--){
                   for (int j = 1;j <= k[i];j++){
                       if (q >= s[i].w[j])
                     dp[q]=max(dp[q],dp[q-s[i].w[j]]+s[i].v[j]);
                 }
             }
         } 
         printf ("%d\n",dp[m]);
     }
}