无空间压缩 -> 有空间压缩

有第三重循环 -> 无第三重循环

算法1

无空间压缩，此时必须要有第三重循环进行决策（会超时），时间复杂度$O(10^9)$

j 由大到小或由小到大都可以

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1010;

int dp[N][N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;

        for (int j = m; j >= 1; j--) {
            for (int k = 0; j - v * k >= 0; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v * k] + w * k);
        }
    }

    cout << dp[n][m];
    return 0;
}

算法2

有空间压缩，有第三重循环（和算法1的时间复杂度相同，但没超时？）

此时 j 必须由大到小

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1010;

int dp[N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;

        for (int j = m; j >= 1; j--) {
            for (int k = 0; j - v * k >= 0; k++)
                dp[j] = max(dp[j], dp[j - v * k] + w * k);
        }
    }

    cout << dp[m];
    return 0;
}

算法3

有空间压缩，无第三重循环，时间复杂度$O(10^6)$

此时 j 必须由小到大

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 1010;

int dp[N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;

        for (int j = v; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }

    cout << dp[m];
    return 0;
}