首先,不考虑步骤,只考虑结果,可以轻(jian)松(nan)地得出一下代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100+5,M=500+5,P=50+5,MINN=0;
int c[N],p[N],w[N][P],f[N][M],ans[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i]>>p[i];
for(int j=1;j<=p[i];j++){
cin>>w[i][j];
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=MINN;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=1;k<=p[i];k++){
if(k*c[i]>j){
f[i][j]=max(f[i][j],f[i-1][j]);
break;
}
f[i][j]=max(f[i][j],max(f[i-1][j],w[i][k]+f[i-1][j-k*c[i]]));
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=0;j<=m;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<f[n][m]<<endl;
return 0;
}
然后加上ans数组,就可以了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100+5,M=500+5,P=50+5,MINN=0;
int c[N],p[N],w[N][P],f[N][M],ans[N][M][N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i]>>p[i];
for(int j=1;j<=p[i];j++){
cin>>w[i][j];
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=MINN;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=1;k<=p[i];k++){
if(k*c[i]>j){
if(f[i-1][j]>f[i][j]){
for(int l=1;l<=n;l++){
ans[i][j][l]=ans[i-1][j][l];
}
}
f[i][j]=max(f[i][j],f[i-1][j]);
break;
}
if(max(f[i-1][j],w[i][k]+f[i-1][j-k*c[i]])>f[i][j]){
if(f[i-1][j]>w[i][k]+f[i-1][j-k*c[i]]){
for(int l=1;l<=n;l++){
ans[i][j][l]=ans[i-1][j][l];
}
}
else{
for(int l=1;l<=n;l++){
ans[i][j][l]=ans[i-1][j-k*c[i]][l];
}
ans[i][j][i]=k;
}
}
f[i][j]=max(f[i][j],max(f[i-1][j],w[i][k]+f[i-1][j-k*c[i]]));
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<ans[i][j]<<" ";
// }
// cout<<endl;
// }
cout<<f[n][m]<<endl;
for(int i=1;i<=n;i++){
cout<<ans[n][m][i]<<endl;
}
return 0;
}