目录

• 零. dp 分析
• 一. 分析
• 二. 代码

零. dp 分析

• 状态表示
  • 集合：所有…的集合
    • 条件：边界、前几个、后几个、体积小于…、时间小于…等（集合的设计带来的一些边界条件）
  • 属性：max、min ......（状态表示了这个集合的什么值？与状态转移相区别）
• 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。

一. 分析

类比完全背包问题的朴素解法，枚举每个物品选几次。这里只不过是枚举每组物品中选择哪个还是不选。

二. 代码

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e2 + 5;

int f[N][N], val[N][N], vol[N][N], num[N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int num_g = 0, container = 0;
    cin >> num_g >> container;

    _rep_le(i, 1, num_g) {
        cin >> num[i];
        _rep_le(j, 1, num[i]) {
            cin >> vol[i][j] >> val[i][j];
        }
    }

    _rep_le(i, 1, num_g) {
        // First i group
        _rep_le(j, 1, container) {
            // Container is j
            // Init f[i][j] with f[i-1][j], which indicates donot choose any item of group i
            f[i][j] = f[i-1][j];
            _rep_le(k, 1, num[i]) {
                // Enumerate whether to choose the Kth item of group i
                if(j >= vol[i][k]) {
                    f[i][j] = max(f[i][j], f[i-1][j-vol[i][k]] + val[i][k]);
                }
            }
        }
    }

    cout << f[num_g][container] << endl;

    return 0;
}