AcWing 9. 分组背包问题
原题链接
中等
作者:
Baitlo
,
2024-03-13 21:36:15
,
所有人可见
,
阅读 11
代码
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
const int N=110;
int v[N][N],w[N][N],f[N],s[N];//v[i][j]存放第i组第j个物品的体积,s[i]存放第i组物品种类数
int n,V;
void init(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
int main(void){
init();
cin>>n>>V;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int k=1;k<=s[i];k++){
cin>>v[i][k]>>w[i][k];
}
}
for(int i=1;i<=n;i++){
for(int j=V;j>=1;j--){
for(int k=1;k<=s[i];k++){
if(v[i][k]<=j) f[j]=max(f[j-v[i][k]]+w[i][k],f[j]);
}
}
}
cout<<f[V];
}