#409. 分组背包问题
分组背包问题
分组背包问题
题目描述
有 组物品和一个容量是 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。第 组的第 件物品体积是 ,价值是 。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输入格式
第一行两个整数 ,分别表示物品组数和背包容量。
接下来有 组数据:
- 每组第一行一个整数 ,表示这一组物品的数量。
- 接下来 行,每行两个整数 ,分别表示一件物品的体积与价值。
输出格式
输出一个整数,表示最大价值。
数据范围
输入样例 1
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例 1
8