题解 | 【模板】01背包

#include <iostream>
#include <vector>
#include <cstring>

#define N 1010

using std::cout;
using std::cin;
using std::vector;

int dp[N], ndp[N];

int main() {
    memset(ndp + 1, 0x80, (N - 1)*sizeof(int));

    int n, m;
    cin >> n >> m;
    int w, v;

    for (int i = 1; i <= n; i++) {
        cin >> w >> v;
        for (int j = m; j >= 0; j--)
            if (j >= w) {
                dp[j] = std::max(dp[j - w] + v, dp[j]);
                ndp[j] = std::max(ndp[j - w] + v, ndp[j]);
            }
    }

    cout << dp[m] << std::endl;
    cout << std::max(0, ndp[m]) << std::endl;

    return 0;
}

优化了空间复杂度