题目描述

有
N
N
组物品和一个容量是
V
V
的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是
v
ij
vij
，价值是
w
ij
wij
，其中
i
i
是组号，
j
j
是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数
N，V
N，V
，用空格隔开，分别表示物品组数和背包容量。
接下来有
N
N
组数据：
每组数据第一行有一个整数
S
i
Si
，表示第
i
i
个物品组的物品数量；
每组数据接下来有
S
i
Si
行，每行有两个整数
v
ij
,
w
ij
vij,wij
，用空格隔开，分别表示第
i
i
个物品组的第
j
j
个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤100
0<N,V≤100

0<
S
i
≤100
0<Si≤100

0<
v
ij
,
w
ij
≤100
0<vij,wij≤100

样例

3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;

const int N=110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];

int main()
{
cin>>n>>m;

for(int i=1;i<=n;i++)
{
    cin>>s[i];
    for(int j=0;j<s[i];j++)
    cin>>v[i][j]>>w[i][j];
}

for(int i=1;i<=m;i++)
    for(int j=m;j>=0;j--)
        for(int k=0;k<s[i];k++)
           if(j>=v[i][k])
           f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

        cout<<f[m]<<endl;

return 0;

}
blablabla

----------

### 算法2
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献


#### C++ 代码

blablabla
```