AcWing 9. 分组背包问题——二维dp表示
原题链接
中等
作者:
朝夕_lin
,
2024-04-05 21:31:45
,
所有人可见
,
阅读 4
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, S = 110;
int n, m;
int v[N][S], w[N][S];
int f[N][N], s[N];
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++)
{
cin >> s[i];
for(int j=1; j<=s[i]; j++) cin>>v[i][j]>>w[i][j];
}
for(int i=1; i<=n; i++)
{
for(int j=1; j <=m; j++)
{
int temp = -1;
for(int k=1; k<=s[i]; k++)
{
if(j >= v[i][k]) temp = max(f[i-1][j-v[i][k]]+w[i][k], temp);
}
f[i][j] = max(f[i-1][j], temp);
}
}
cout << f[n][m];
return 0;
}