一维

#include <bits/stdc++.h>
using namespace std;
const int N = 30 + 10, M = 200 + 10;
int f[M];
int v[N], w[N];
int n, m;

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

二维

#include <bits/stdc++.h>
using namespace std;
const int N = 30 + 10, M = 200 + 10;
int f[2][M];
int v[N], w[N];
int n, m;

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

滚动

#include <bits/stdc++.h>
using namespace std;
const int N = 30 + 10, M = 200 + 10;
int f[2][M];
int v[N], w[N];
int n, m;

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