朴素版

#include<iostream>
using namespace std;
const int M=6010;

int n,m;
int f[M];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        for(int j=m;j>=0;j--)
            for(int k=0;k<=s&&k*v<=j;k++)
            f[j]=max(f[j],f[j-k*v]+k*w);
    }
    cout<<f[m];
    return 0;
}

单调队列优化

#include<iostream>
#include<cstring>
using namespace std;
const int M=6010;

int n,m;
int f[M],g[M];
int q[M];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        memcpy(g,f,sizeof f);
        for(int j=0;j<v;j++)
        {
            int hh=0,tt=-1;
            for(int k=j;k<=m;k+=v)
            {
                while(hh<=tt&&g[q[tt]]<=g[k]-(k-q[tt])/v*w)
                tt--;
                q[++tt]=k;
                if(hh<=tt&&k-v*s>q[hh])
                hh++;
                f[k]=g[q[hh]]+(k-q[hh])/v*w;
            }
        }
    }
    cout<<f[m];
    return 0;
}