01背包问题-二维空间

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, V = 1010;
int f[N][V];
int n, v;

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

    return 0;
}

01背包-一维空间优化

```
#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
const int N = 1010, V = 1010;
int f[V];
int n, v;

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

```