类似01背包，背包状态有放1，2，...种情况

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int w[N],v[N],f[N][N];

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
            {
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }

    cout<<f[n][m];        
}



注意到，代码套了三层循环，直接tle
优化：
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i].)
f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-v[i]*2]+w[i],f[i-1][j-3*v[i]]+2*w[i])

联立：f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])
对比01背包：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
因此还可以像01背包那样再次优化

#include<iostream>
#include<algorihtm>
using namespace std;
const int N=1010;

int v[N],w[N],f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);   
        }

        cout<<f[m];
}