方法一：常规做法$O(n^3)$

• f[i][j]表示只使用前i个物品且总体积为j的情况下能得到的最大价值
• f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i], f[i - 1][j - 2 * v[i]] + 2 * w[i], … , f[i - 1][j - k * v[i]] + k * w[i])

#include <iostream>
using namespace std;

const int N = 1010;
int f[N][N];

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

方法二：优化$O(n^2)$

#include <iostream>
using namespace std;

const int N = 1010;
int f[N];
// f[j]表示只使用j的体积下，每个物品可以选择任意多次所能获得的最大价值
int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        int v, w; cin >> v >> w;
        for(int j = v; j <= m; j ++ )
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m] << endl;
    return 0;
}