2919. 分组背包问题
时间限制：1000 MS 内存限制：64 MB
题目描述
# 分组背包问题 ## 题目描述 有 $N$ 组物品和一个容量为 $V$ 的背包。第 $i$ 组有 $S_i$ 件物品，其中第 $j$ 件物品的体积为 $v_{ij}$，价值为 $w_{ij}$。 每组物品最多只能选择一件，也可以不选。请在所选物品总体积不超过背包容量 $V$ 的前提下，使所选物品的总价值最大。 输出这个最大总价值。 ## 输入格式 从文件 `groupknap.in` 中读入数据。 第一行包含两个整数 $N$ 和 $V$，用空格隔开，分别表示物品组数和背包容量。 接下来输入 $N$ 组数据。第 $i$ 组数据的格式如下： - 第一行包含一个整数 $S_i$，表示第 $i$ 组的物品数量。 - 接下来 $S_i$ 行，每行包含两个整数 $v_{ij}$ 和 $w_{ij}$，用空格隔开，分别表示第 $i$ 组中第 $j$ 件物品的体积和价值。 ## 输出格式 输出到文件 `groupknap.out` 中。 输出一个整数，表示所选物品总体积不超过 $V$ 且每组最多选择一件物品时，可以获得的最大总价值。 ## 数据范围 所有输入数据均为整数，且满足： - $1 \le N,V \le 100$； - $1 \le S_i \le 100$； - $1 \le v_{ij},w_{ij} \le 100$。 ## 样例输入 ``` 3 5 2 1 2 2 4 1 3 4 1 4 5 ``` ## 样例输出 ``` 8 ``` ## 样例说明 选择第 $1$ 组中体积为 $2$、价值为 $4$ 的物品，以及第 $2$ 组中体积为 $3$、价值为 $4$ 的物品，不选择第 $3$ 组的物品。 所选物品的总体积为 $5$，总价值为 $8$，这是可以获得的最大总价值。 ## 时间与空间限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。