想用完全背包,然后爆零
求调
#include <bits/stdc++.h>
using namespace std;
int t,n,m;
int w[101][101],f[101][1001];
int main()
{
memset(f,0,sizeof(0));
memset(w,0,sizeof(0));
scanf("%d%d%d",&t,&n,&m);
for(int k=1;k<=t;k++)
{
for(int i=1;i<=n;i++)
{
cin>>w[k][i];
}
}
for(int s=1;s<=t-1;s++)
{
for(int i=1;i<=n;i++)
{
int c=w[s+1][i]-w[s][i];
for(int j=1;j<=m;j++)
{
if(j>=w[s][i])
{
for(int k=1;k*w[s][i]<=j;k++)
{
f[i][j]=max(f[i-1][j],f[i-1][j-k*w[s][i]]+k*c);
}
}
else f[i][j]=f[i-1][j];
}
}
m=f[n][m];
}
cout<<f[n][m];
return 0;
}