背包

0-1背包

模版

一维二维

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> w(N), d(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> w[i] >> d[i];
    }
    vector<int> dp(M + 1);
    for (int i = 0 ; i < N ; i++) {
        for (int j = M ; j >= w[i] ; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + d[i]);
        }
    }
    cout << dp[M] << "\n";
    return 0;
}

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> w(N), d(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> w[i] >> d[i];
    }
    vector<vector<int>> dp(N + 1, vector<int>(M + 1));
    for (int i = 1 ; i <= N ; i++) {
        for (int j = 0 ; j <= M ; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = M ; j >= w[i - 1] ; j--) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + d[i - 1]);
        }
    }
    cout << dp[N][M] << "\n";
    return 0;
}

例题

洛谷P2871(求最优值)AcWing278(求体积恰好为M的方案数)AcWing11(求最优方案数)AcWing12(求具体方案)

P2871 [USACO07DEC] Charm Bracelet S - 洛谷

278. 数字组合 - AcWing

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> v(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> v[i];
    }
    vector<int> dp(M + 1);
    dp[0] = 1;
    for (int i = 0 ; i < N ; i++) {
        for (int j = M ; j >= v[i] ; j--) {
            dp[j] = dp[j] + dp[j - v[i]];
        }
    }
    cout << dp[M] << "\n";
    return 0;
}

11. 背包问题求方案数 - AcWing

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
const long long mod = 1000000007;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> v(N), w(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> w[i] >> v[i];
    }
    vector<long long> dp(M + 1), g(M + 1);
    g[0] = 1;
    for (int i = 0 ; i < N ; i++) {
        for (int j = M ; j >= w[i] ; j--) {
            long long k;
            long long temp = dp[j - w[i]] + v[i];
            if (dp[j] < temp) {
                g[j] = g[j - w[i]];
                dp[j] = temp;
            } else if (dp[j] == temp) {
                g[j] = (g[j] + g[j - w[i]]) % mod;
            }
        }
    }
    long long res = 0;
    for (int i = 0 ; i <= M ; i++) {
        res = max(res, dp[i]);
    }
    long long ans = 0;
    for (int i = 0 ; i <= M ; i++) {
        if (dp[i] == res) {
            ans = (ans + g[i]) % mod;
        }
    }
    cout << ans;
    return 0;
}

12. 背包问题求具体方案 - AcWing

编号正序编号逆序

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> v(N), w(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> w[i] >> v[i];
    }
    vector<vector<long long>> dp(N + 1, vector<long long>(M + 1));
    for (int i = N - 1 ; i >= 0 ; i--) {
        for (int j = 0 ; j <= M ; j++) {
            dp[i][j] = dp[i + 1][j];
        }
        for (int j = M ; j >= w[i] ; j--) {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
        }
    }
    vector<int> ans;
    for (int i = 0, j = M ; i < N ; i++) {
        if (j >= w[i] && dp[i][j] == dp[i + 1][j - w[i]] + v[i]) {
            ans.emplace_back(i + 1);
            j -= w[i];
        }
    }
    for (auto &i : ans) {
        cout << i << " ";
    }
    return 0;
}

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> v(N), w(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> w[i] >> v[i];
    }
    vector<vector<long long>> dp(N + 1, vector<long long>(M + 1));
    for (int i = 1 ; i <= N ; i++) {
        for (int j = 0 ; j <= M ; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = M ; j >= w[i - 1] ; j--) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
    vector<int> ans;
    for (int i = N - 1, j = M ; i >= 0 ; i--) {
        if (j >= w[i] && dp[i + 1][j] - v[i] == dp[i][j - w[i]]) {
            ans.emplace_back(i + 1);
            j -= w[i];
        }
    }
    for (auto &i : ans) {
        cout << i << " ";
    }
    return 0;
}

完全背包

模版

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> w(n), v(n), dp(m + 1);
    for (int i = 0 ; i < n ; i++) cin >> w[i] >> v[i];
    for (int i = 0 ; i < n ; i++) {
        for (int j = w[i] ; j <= m ; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[m];
    return 0;
}

例题

AcWing3(求最优值)

3. 完全背包问题 - AcWing

多重背包

模版

二进制优化单调队列优化

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> v(n), w(n), s(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }
    vector<long long> nv, nw;
    for (int i = 0 ; i < n ; i++) {
        long long temp = 1;
        long long k = s[i];
        while (k > temp) {
            k -= temp;
            nv.emplace_back(v[i] * temp);
            nw.emplace_back(w[i] * temp);
            temp <<= 1;
        }
        if (k) {
            nv.emplace_back(v[i] * k);
            nw.emplace_back(w[i] * k);
        }
    }
    vector<long long> dp(m + 1);
    int len = nv.size();
    for (int i = 0 ; i < len ; i++) {
        for (int j = m ; j >= nw[i] ; j--) {
            dp[j] = max(dp[j], dp[j - nw[i]] + nv[i]);
        }
    }
    cout << dp[m] << "\n";
    return 0;
}

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int q[1000005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> v(n), w(n), s(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> w[i] >> v[i] >> s[i];
    }
    vector<vector<long long>> dp(2, vector<long long>(m + 1));
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < w[i] ; j++) {
            int L = 0, R = -1;
            for (int k = j ; k <= m ; k += w[i]) {
                while (L <= R && k - 1LL * s[i] * w[i] > q[L]) {
                    L++;
                }
                while (L <= R && dp[i & 1][q[R]] + (k - q[R]) / w[i] * v[i] <= dp[i & 1][k]) {
                    R--;
                }
                q[++R] = k;
                dp[i & 1 ^ 1][k] = dp[i & 1][q[L]] + (k - q[L]) / w[i] * v[i];
            }
        }
    }
    cout << dp[n & 1][m] << "\n";
    return 0;
}

例题

AcWing5(二进制优化)AcWing6(单调队列优化)

5. 多重背包问题 II - AcWing

6. 多重背包问题 III - AcWing

二维费用背包

同 0-1 背包

例题

洛谷P1855

P1855 榨取kkksc03 - 洛谷

分组背包

例题

洛谷P1757

P1757 通天之分组背包 - 洛谷

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> M >> N;
    map<int, vector<int>> v, w;
    for (int i = 0 ; i < N ; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        w[z].emplace_back(x);
        v[z].emplace_back(y);
    }
    vector<int> dp(M + 1);
    for (auto& [g, ww] : w) {
        auto& vv = v[g];
        for (int i = M ; i >= 0 ; i--) {
            int len = ww.size();
            for (int j = 0 ; j < len ; j++) {
                if (i >= ww[j]) {
                    dp[i] = max(dp[i], dp[i - ww[j]] + vv[j]);
                }
            }
        }
    }
    cout << dp[M];
    return 0;
}

多人背包(k优解)

例题

洛谷P1858

P1858 多人背包 - 洛谷

C++
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k, m, n;
    cin >> k >> m >> n;
    vector<int> w(n), v(n);
    for (int i = 0 ; i < n ; i++) {
        cin >> w[i] >> v[i];
    }
    vector<vector<int>> dp(k, vector<int>(m + 1, 0x7fffffff + 1));
    vector<int> re(k);
    dp[0][0] = 0;
    for (int i = 0 ; i < n ; i++) {
        for (int j = m ; j >= w[i] ; j--) {
            int a = 0, b = 0, t = 0;
            while (t < k) {
                if (dp[a][j] >= dp[b][j - w[i]] + v[i]) {
                    re[t++] = dp[a++][j];
                } else {
                    re[t++] = dp[b++][j - w[i]] + v[i];
                }
            }
            for (int L = 0 ; L < k ; L++) {
                dp[L][j] = re[L];
            }
        }
    }
    int ans = 0;
    for (int i = 0 ; i < k ; i++) ans += dp[i][m];
    cout << ans << "\n";
    return 0;
}