二维数组

复杂度： $O(nmk)=O(m\sum_i^n s_i)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 1e3 + 5, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, m, v[N], w[N], f[N][M];

int main(int argc, char* argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // DP
    // 1. 初始化  f[i][j]=0
    for (int i = 1; i <= n; i++)                 // 阶段
        for (int j = 0; j <= m; j++)             // 容量
            for (int k = 0; k <= m / v[i]; k++)  // 选 k 件
                if (j - k * v[i] >= 0)
    f[i][j] = max(f[i - 1][j], f[i - 1][j - k * v[i]] + k * w[i]);
    // 目标
    cout << f[n][m];
    return 0;
}

时间优化

复杂度： $O(nm)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 1e3 + 5, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, m, v[N], w[N], f[N][M];

int main(int argc, char* argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // DP
    // 1. 初始化  f[i][j]=0
    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][j - v[i]] + w[i]);
        }
    // 目标
    cout << f[n][m];
    return 0;
}

状态压缩

复杂度： $O(nm)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 1e3 + 5, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, m, v[N], w[N], f[M];

int main(int argc, char* argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // DP
    // 1. 初始化  f[j]=0
    for (int i = 1; i <= n; i++)      // 阶段
        for (int j = v[i]; j <= m; j++)  // 容量
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    // 目标
    cout << f[m];
    return 0;
}