01背包朴素解法

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N];
int w[N],v[N];
int main()
{

    int n, m;
    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;
}

01背包优化解法

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int w[N], v[N];
int main()
{

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        //把if的条件移到这里j>=v[i]
        for (int j = m; j >= v[i]; j--) {
            //f[j]=f[j]
            //f[i][j]=f[i-1][j];

            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
            //如果不改成从大到下枚举，那么j-v[i]一定比j小
            //则从小到大枚举 在计算f[j]的前面就已经算出了f[j-v[i]]

        }
    }
    cout << f[m] << endl;
    return 0;
}