暴力

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;

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

// 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]] + w[i] ....)
// f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])

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][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];

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 = v[i]; j <= m; j++){
            // f[i][j] = f[i - 1][j];
            // 由于需要的是f[i][j - v[i]]
            // 从小到大 j - v[i] < j 所以 j - v[i] 会先算，计算的就是f[i][j - v[i]] 的情况
            // 与01背包区别：第二维度j遍历顺序相反
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    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];

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][j - v[i]] + w[i]);
        }
    cout << f[n & 1][m] << endl;
    return 0;
}