弱鸡的一点点题解，直接看关键部分的注释即可！

由于只用到了当前层的v[i]和w[i]所以可以不用开数组，直接变输入边更新数组即可，懒得改变了！

• 推荐使用第三种二进制优化，最易理解！

暴力DP（最易理解）

#include <iostream>
#include <algorithm>

using namespace std;

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

int main(){
    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[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

一位数组优化版本（不太好理解）

#include <iostream>
#include <algorithm>

using namespace std;

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

// 滚动数组优化：
// 1. f[i][j]的计算只用到f[i - 1][]的情况
// 2. 第二维j只会用到小于等于j的情况
// 其实说实话：这样的优化空间会好一点，但思想难度加了不是一点点，最大的好处就是拓宽思路，学习逻辑和想法，前人及y总的智慧结晶
// 效果相同但更好理解的做法，使用二维数组，定义为f[2][N]即可，使用二进制来控制第一维度即可

int main(){
    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 j = m; j >= v[i]; j--){
            // f[i][j] = f[i - 1][j];
            // f[j] = f[j]; 将上一层i - 1的情况赋值到i层
            // 对于这里的处理，就是一个赋值处理，由于之后计算要用到f[j]并且此时的转态为i - 1层的状态转移而来，不需要任何处理

            // if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            // j >= v[i]写到循环条件 保证上一行一定有意义
            f[j] = max(f[j], f[j - v[i]]+ w[i]);
            // 1. j从v[i] ~ m时，由于j - v[i] < j，所以j - v[i]会在计算j的状态之前被计算，即他会计算i, i - 1, i - 2 ... 的状态的最优值，即f[i][j],但是我们需要的是f[i - 1][j]，即要保证在计算j的状态时，j - v[i]不能被更新，应该保持上一层i - 1的状态，（简而言之：就是在计算j - v[i]的次序一定要处于j之后）
            // 2. 解决方法：逆序计算，即可保证j - v[i] 在 j 之后被计算，此时j - v[i]保存的就是i层状态计算之前的最优值，即f[i - 1][j]
        }
    }
    cout << f[m] << endl;

    return 0;
}

二进制滚动数组优化（好理解）

#include <iostream>
#include <algorithm>

using namespace std;

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

// 变化：将第一维都 & 1 即可

int main(){
    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[i & 1][j] = f[(i - 1) & 1][j];
            if(j >= v[i]) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}