Acwing 2. 01背包问题

 f[i][j]表示从前i个物品选，总体积<=j的所有选法中的最大值。

注意，当j<Vi时，表示装不下第i个物品，需要单独判断一下

状态计算：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])

将集合划分为：选第i个物品 和 不选第i个物品 两部分

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++ i) scanf("%d %d", &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]);
        }
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; ++ i) scanf("%d %d", &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]);
        }
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

采用滚动数组优化时，f[j - v[i]] 是前i - 1个(f[i - 1][j - v[i]])的选法，如果j循环从v[i]到m, 则会在计算f[j]之前算出来，此时f[j - v[i]]表示的是前i个(f[i][j - v[i]])的选法，是错误的，所以，应该将j循环从m倒循环到v[i],确保f[j - v[i]]在计算f[j]之前没有被修改过。