一共有n组,每组里面有s个,每次只能从一组中选一个。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N][N],S[N];
int V[N][N],W[N][N];
int n,m;
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++){
//不选
f[i][j] = f[i - 1][j];
for(int k=0;k<=S[i];k++){
//选
if(V[i][k] <= j)
f[i][j]=max(f[i][j],f[i - 1][j-V[i][k]] + W[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
同样可以优化成一维
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int f[N],S[N];
int V[N][N],W[N][N];
int n,m;
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 = m; j >= 0; j--){
for(int k = 1; 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];
return 0;
}
评论区