1
2
3
4
5
6
7
8

2 5
3
1 1
2 2
3 3
2
1 2
2 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for( int i =1;j<=N;i++){
    //初始化j=0时,每个容量都应该是
    for(int k = 0 ; k<=C ; k++)
        f[i][k] = f[i-1][k];
    for( int j =1;j<=total(i);j++){
    for(int k = 1 ;k <= C;k++) { // 枚举容量

            //不选j的价值
            
            if( k>= w[i][j] )
                f[i][w] = max(f[i-1][W-w[i][j]] + v[i][j],f[i][w]);

        } // end for j
    } //end for k
} // end for i

1
2
3
4
5
6
7
8
9
10
11
12
13

for( int i =1;j<=N;i++){
    for(int k = 1 ;k <= C;k++) { // 枚举容量
        f[i][k] = f[i-1][k];
        for( int j =1;j<=total(i);j++){

            //不选j的价值
            
            if( k>= w[i][j] )
                f[i][w] = max(f[i-1][W-w[i][j]] + v[i][j],f[i][w]);

        } // end for j
    } //end for k
} // end for i

1
2
3

枚举组i
    倒序枚举容量C
        处理第i组内的每个物品在当前容量下的最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// desc: 分组背包的模板代码
// author:rainboy 
// date: 2023/4/26

#define FOR(i,a,b) for(int i = a ; i<= b; ++i)
#define rFOR(i,a,b) for(int i = a ; i>= b; --i)


// cap 背包的容量
template<int Cap,int MaxStuff>
struct groupKnapsack {
   long long f[Cap+5]; //f[i] 在容量为i的条件下得到的最大值

   struct stuff { int w,v; }; //一个物品的重量与价值
   int stuff_size;
   stuff stuffs[MaxStuff+5]; //存一组物品

   //清空一组背包
   void clear() { stuff_size = 0;}

   //添加一个物品 
   void push(int w,int v){
        stuffs[++stuff_size] = {w,v};
   }

   // 处理一个物品
   void deal_one_stuff(int v,int w,int c){
        if( c < w ) return; //容量不够
        if( f[c] < f[c-w]+v) f[c] = f[c-w]+v;
   }

   //处理一组物品
   void deal_one_group_stuff() {
        rFOR(C,Cap,0) // 容量 大->小
            FOR(i,1,stuff_size) //枚举物品 
                deal_one_stuff(stuffs[i].v,stuffs[i].w,C);
   }

   //得到答案
   long long ans(int cap=Cap) {
       return f[cap];
   }
};

1
2
3
4
5
6
7
8
9
10

3 6
3
3 4
2 3
4 2
2
1 4
2 5
1
4 3

1

9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

// desc: 分组背包的模板代码
// author:rainboy 
// date: 2023/4/26
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = a ; i<= b; ++i)
#define ROF(i,a,b) for(int i = a ; i>= b; --i)


// cap 背包的容量
template<int Cap,int MaxStuff>
struct groupKnapsack {
   long long f[Cap+5]; //f[i] 在容量为i的条件下得到的最大值

   struct stuff { int w,v; }; //一个物品的重量与价值
   int stuff_size;
   stuff stuffs[MaxStuff+5]; //存一组物品

   //清空一组背包
   void clear() { stuff_size = 0;}

   //添加一个物品 
   void push(int w,int v){
        stuffs[++stuff_size] = {w,v};
   }

   // 处理一个物品
   void deal_one_stuff(int v,int w,int c){
        if( c < w ) return; //容量不够
        if( f[c] < f[c-w]+v) f[c] = f[c-w]+v;
   }

   //处理一组物品
   void deal_one_group_stuff() {
        ROF(C,Cap,0) // 容量 大->小
            FOR(i,1,stuff_size) //枚举物品 
                deal_one_stuff(stuffs[i].v,stuffs[i].w,C);
   }

   //得到答案
   long long ans(int cap=Cap) {
       return f[cap];
   }
};


int n; // n组
int C; //最大容量

// 创建一个 最大容量6,一组物品最多5个的 背包
groupKnapsack<6, 5> mybp;

int main(){
    cin >> n >> C;
    FOR(i,1,n){
        int t;
        cin >> t;
        mybp.clear();
        FOR(j,1,t){
            int w,v;
            cin >> w >> v;
            mybp.push(w,v);
        }
        mybp.deal_one_group_stuff();
    }

    cout << mybp.ans(C) << '\n';

    return 0;
}