背包问题总结

一、求最大价值模型

1. 01背包

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int n, V;

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

2. 完全背包

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int n, V;

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = v[i]; j <= V; j++) { // 与01背包的唯一一点不同
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[V] << endl;
    return 0;
}

3. 多重背包1

0 < N, V ≤ 100
0 < vi, wi, si ≤ 100

时间复杂度O(1e6) ：时间复杂度比较小，直接暴力写即可

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

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

int n, V;

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

4. 多重背包2

0 < N ≤ 1000
0 < V ≤ 2000
0 < vi, wi, si ≤ 2000

二进制优化

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1010, M = 2010;

struct Good {
    int v, w;
};

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

int n, V;

int main() {
    vector<Good> goods;
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= s[i]; k *= 2) {
            s[i] -= k;
            goods.push_back({k * v[i], k * w[i]});
        }
        if (s[i] > 0) goods.push_back({s[i] * v[i], s[i] * w[i]});
    }
    for (auto i : goods) {
        for (int j = V; j >= i.v; j--) {
            f[j] = max(f[j], f[j - i.v] + i.w);
        }
    }
    cout << f[V] << endl;
    return 0;
}

5. 多重背包3 （男人八题）

0 < N ≤ 1000
0 < V ≤ 20000
0 < vi, wi, si ≤ 20000

单调队列优化

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 20010;

int v[N], w[N], s[N];
int f[M], g[M], q[M];

int n, V;

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i ++ ) {
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v[i]; j++) {
            int hh = 0, tt = -1;
            for (int k = j; k <= V; k += v[i]) {
                if (hh <= tt && q[hh] < k - s[i] * v[i]) hh++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v[i] * w[i] <= g[k] - (k - j) / v[i] * w[i]) tt -- ;
                q[++tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[V] << endl;
    return 0;
}

6. 分组背包

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

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

int n, V;

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

7. 混合背包

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int n, V;

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

8. 二维费用背包

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010, MM = 110;

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

int n, V, M;

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

9. 有依赖的背包问题

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 110;

int v[N], w[N];
int f[N][N];
// f[u][j]表示所有以u为根的子树，背包容量为j的最大价值

int h[N], e[N], ne[N], idx;
// h[i]    : 第i个节点的第一条邻边idx
// e[idx]  : 存储idx这条边的终点
// ne[idx] : 存储与第idx这条边同起点的下一条边的idx

int n, V;

void add(int a, int b) { // 邻接表的方式来存储
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) { // 在第u个节点下
    for (int i = h[u]; i != -1; i = ne[i]) {
        int son = e[i];
        dfs(e[i]);
        for (int j = V - v[u]; j >= 0; j--) {
            for (int k = 0; k <= j; k++) { // 金明的预算方案是按照每一种方案来进行枚举的，而这是从集合的角度
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]); // 递归式思考
            }
        }
    }
    for (int i = V; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u]; // 将物品u加进去
    for (int i = 0; i < v[u]; i++) f[u][i] = 0; // 剩余背包容量 < 第u个节点的空间，那么该节点下边的所有节点均不能选
}

int main() {
    cin >> n >> V;
    memset(h, -1, sizeof(h));
    int root;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> v[i] >> w[i] >> p;
        if (p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout << f[root][V] << endl;
    return 0;
}

Important

// 状态定义：基于最大价值（f[V]表示背包容量为V的情况下所能容纳的最大价值）
背包容量不超过V，全都初始化0
背包容量恰好为V，f[0, 0] = 0, f[0, i] = +∞/-∞ (看题目是求最大值还是最小值), j >= v
背包容量至少为V，f[0, 0] = 0, f[0, i] = +∞/-∞ (看题目是求最大值还是最小值), j无条件限制

状态从第i - 1层转移过来，体积要从大到小枚举；从第i层转移过来，体积从小到大枚举

二、背包问题求方案数

类似于 278. 数字组合 这道题的求方案数直接写即可，状态定义由原来的求最大价值转为求方案数即可

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;

int v[N];
int f[N];

int n, m;

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

最优选法的方案数： 11. 背包问题求方案数

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, mod = 1e9 + 7;

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

int n, V;

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    memset(f, -0x3f, sizeof(f)); // 注意将背包容量看做“恰好”
    f[0] = 0;
    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            int maxv = max(f[j], f[j - v[i]] + w[i]);
            int cnt = 0;
            if (maxv == f[j]) cnt += g[j];
            if (maxv == f[j - v[i]] + w[i]) cnt += g[j - v[i]];
            g[j] = cnt % mod;
            f[j] = maxv;
        }
    }

    int res = 0;
    for (int i = 0; i <= V; i++) res = max(res, f[i]);

    int cnt = 0;
    for (int i = 0; i <= V; i++) {
        if (res == f[i]) cnt = (cnt + g[i]) % mod;
    }
    cout << cnt << endl;
    return 0;
}

三、背包问题求具体方案

直接上题目链接吧，累了不想写了，其实也没写什么qwq（记录一下，今天是2024.5.13）
12. 背包问题求具体方案
求具体方案不能状态压缩

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

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

int n, V;

int main() {
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    // 求具体方案得将物品反着枚举，这样可以从第一个物品一直推到最后一个物品是否被选
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= V; 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]);
        }
    }
    // 此时f[1][V]为最大值
    int j = V;
    for (int i = 1; i <= n; i++) {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {
            cout << i << ' ';
            j -= v[i];
        }
    }
    return 0;
}