AcWing 9. 分组背包问题
原题链接
中等
作者:
大鼻孔
,
2021-12-05 23:23:37
,
所有人可见
,
阅读 280
打卡背包
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int n,m;
int v[N][N],w[N][N];
int s[N];
int f[N][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];
}
//从第i个物品中选,总体积不超过j的选法的max
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=0;k<s[i];k++)
{
if(j-v[i][k]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
that all for it
thanks for watching