一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1e3+10;

int n, m;
int v[N], w[N];

class DP
{
public:
    int f[2][N];
    //由于只用到i层和i-1层，所以可以只存两层内容

public:
    DP()
    {
        initIO();
        fill(f[0], f[0]+2*N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    int work()
    {
        for(int i=1;i<=n;++i)
            for(int j=0;j<=m;++j)
            {
                f[i&1][j]=f[i-1&1][j];//i层第一次为0，所以赋值即可
                if(j>=v[i])//不能让j的初始值为v[i], 因为还有不选的状态转移
                    f[i&1][j]=max(f[i&1][j], f[i-1&1][j-v[i]]+w[i]);
            }

        return f[n&1][m];
    }
}dp;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>v[i]>>w[i];
    cout<<dp.work();
}