背包九讲

动态规划

视频资料

01背包问题（一件物品选或者不选）

普通版本

表示只看前 i 个物品，背包容量为 j 时，总价是最大是多少

集合划分:

1. 不选第 i 个物品，
2. 选第 i 个物品，

: 0

一维数组版本

表示 体积为 i 的情况下，最大价值是多少
二维版本，，如果直接去掉第一维，那么 实际上记录的是 的状态，因为 这个方程中， 一定比 小，所以一定在这之前算过，所以这个状态实际上是 的状态。
那么 j 从大到小枚举即可，因为 ，所以 j 一定在 前计算，所以 用到的便是 i - 1 的状态
正确性：从后往前枚举，和从前往后枚举都一样，因为算 f[i][j] 时，用到的一定是 f[i - 1] 的某个状态，和 f[i] 的所有状态无关，所以从大往小，从小往大都一样

求解体积恰好为 V 的最大价值

只要初始化时， 即可，这样就保证了，状态一定由 拓展过来
为什么全初始化为 0 时，不是体积恰好为 j 时的最大价值呢？
因为全为 0 时，如果答案 m < V，最优状态既可以从 0 扩展到 m，也可以从 V - m 扩展到 V，因为 dp[0] 和 dp[V - m] 都是 0

完全背包问题（每件物品可以选无限次）

表示：总体积为 i 的情况下，最大价值是多少

那么只需要把 01背包的 代码，让 j 从小到大就可以达成每件物品选无限次
j 从大到小时， 保证了用到的状态一定是二维时 i - 1 的状态
j 从小到大时， 就是， j = v[i] 时，用到了 i - 1 的状态，后续都是用的 i 的状态，而物品还是第 i 个，所以就达成了可以选无限次
证明从小到大的正确性：

1. 假设考虑前 i-1 个物品后，所有的 都是正确的
2. 证明，考虑完第 i 个物品后，所有的 也都是正确的

对于某个 j 而言，如果最优解里有 k 个 v[i]
那么从小到大枚举， 会被最先枚举到，可以由 更新，但更新不了
然后接着往后，到了 被枚举到了，会由 更新，这就有了一个 v[i]
然后以此类推，到了 ，会由 更新，会有 k 个 v[i]，即证明了从小到大枚举可以达到,从大到小枚举，但每个物品枚举 k 次的效果

多重背包问题（每件物品有独特限制）

总体积为 i 的时候，最大价值是多少

N^3 复杂度做法

与完全背包类似， 只是把 k 再做个限制

二进制优化 N^2 * LogN

先转化成 01背包问题，就是把1个物品拆成s份，但这样太慢，可以考虑二进制拆法，非二进制幂就普通拆就好，比如 8，拆成1 2 4 1
这样总的时间复杂度就变成了 1e8 这种级别，能过了

单调队列优化

首先是为什么可以做到NV 的复杂度
对枚举的 j 进行分组，使得处理一组的时间是线性，所有的分组处理完，时间复杂度也是线性（V/v v）
组内怎样做到 O(1) 时间状态转移的
原始转移方程是

分组后

看不出来，可以让

之后

这样就能发现，维护一个窗口大小为 s+1 的窗口，每次取最大值，结果再加上 kw

#pragma GCC optimize(2)
#include <iostream>
#include <deque>
using namespace std;
const int MAXN = 20000 + 5;
struct Node {
    int pos, val;
};
int dp[MAXN];
int main() {
    int N, V;
    cin >> N >> V;
    int v, w, s;
    for (int i = 0; i < N; i++) {
        cin >> v >> w >> s;
        for (int i = 0; i < v; i++) {
            deque<Node> q;
            int stop = (V-i)/v;
            for (int k = 0; k <= stop; k++) {
                int val = dp[k*v+i] - k*w;
                while (!q.empty() && k - q.front().pos > s) q.pop_front(); // 大小为 s + 1 的窗口
                while (!q.empty() && val >= q.back().val) q.pop_back();
                q.push_back({k, val});
                dp[k*v+i] = q.front().val + k*w;
            }
        }
    }
    cout << dp[V] << endl;
}

混合背包问题（物品有很多种（3种））

分开讨论就好，判断物品属于那种，dp数组用一个，然后用三种背包策略去解决对应的物品

二维费用的背包问题

和 01背包问题类似，转移的时候注意一下就好

#include <iostream>
using namespace std;
const int MAXN = 1000;
int dp[MAXN][MAXN];
int main() {
    int N, V, M;
    cin >> N >> V >> M;
    int v, m, w;
    while (N--) {
        cin >> v >> m >> w;
        for (int i = V; i >= v; i--)
            for (int j = M; j >= m; j--)
                dp[i][j] = max(dp[i][j], dp[i - v][j - m] + w);
    }
    cout << dp[V][M] << endl;
}

分组背包问题（物品分组后，每组只能选一个）

和 01背包类似，不过是每组求一个，且组内互斥

#include <iostream>
using namespace std;
const int MAXN = 100 + 5;
int dp[MAXN], v[MAXN], w[MAXN];
int main() {
    int N, V;
    cin >> N >> V;
    int s;
    while (N--) {
        cin >> s;
        for (int i = 0; i < s; i++) cin >> v[i] >> w[i];
        for (int i = V; i >= 0; i--)
            for (int j = 0; j < s; j++)
                if (i >= v[j]) dp[i] = max(dp[i], dp[i - v[j]] + w[j]);
    }
    cout << dp[V] << endl;
}

背包问题求方案数

与 传统背包问题类似，不过需要加一个数组，用来做 方案数的转移
还需要注意一点，-INF，这样能保证所有的状态都是从 0 转移过去的，f[j] 的意义就变成了，背包体积恰好为 j 的情况下，最大价值是多少

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int f[MAXN], g[MAXN];
int main() {
    int N, V;
    cin >> N >> V;
    g[0] = 1, f[0] = 0;
    for (int i = 1; i <= N; i++) f[i] = -INF;

    int v, w;
    while (N--) {
        cin >> v >> w;
        for (int i = V; i >= v; i--) {
            int s = max(f[i], f[i - v] + w);
            int t = 0;
            if (s == f[i]) t = g[i];
            if (s == f[i - v] + w) t += g[i - v];

            if (t >= MOD) t -= MOD;
            f[i] = s, g[i] = t;
        }
    }

    int idx = max_element(f, f + 1 + V) - f;
    int ans = 0;
    for (int i = 0; i <= V; i++) if (f[i] == f[idx]) ans = (ans + g[i]) % MOD;

    cout << ans << endl;
}

求背包问题方案

这里需要反着来一下，转移方程变成了

为什么？因为需要输出的方案是字典序最小的，这样的话，就可以从第一个物品开始找

#include <iostream>
using namespace std;
const int MAXN = 1000 + 5;
int dp[MAXN][MAXN];
int v[MAXN], w[MAXN];
int main() {
    int N, V;
    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++)
            if (j >= v[i]) dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - v[i]] + w[i]);
            else dp[i][j] = dp[i + 1][j];

    int val = V;
    for (int i = 1; i <= N; i++)
        if (val - v[i] >= 0 && dp[i][val] == dp[i + 1][val - v[i]] + w[i]) {
            cout << i << ' ';
            val -= v[i];
        }
}

有依赖的背包问题

dp[i][j]，表示以 i 为根节点的字数，体积大小不大于 j 时，最大价值是多少
对于一棵树，所有以他子节点为根的子树算完以后，把子节点的所有 体积 看成一组，这个问题就转换成了 分组背包问题
但需要注意根节点本身一定要选的问题

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100 + 5;
int dp[MAXN][MAXN];
vector<int> g[MAXN];
int v[MAXN], w[MAXN];
int N, V;
void dfs(int x) {
    for (int i = v[x]; i <= V; i++) dp[x][i] = w[x];  // 把所有能选根的，都默认选上根，因为根一定要选嘛
    for (auto y : g[x]) {
        dfs(y);
        for (int j = V; j >= v[x]; j--)
            for (int k = 0; k <= j - v[x]; k++)
                dp[x][j] = max(dp[x][j], dp[x][j - k] + dp[y][k]);
    }
}
int main() {
    cin >> N >> V;
    int root, fa;
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i] >> fa;
        if (fa == -1) root = i;
        else g[fa].push_back(i);
    }
    dfs(root);
    cout << dp[root][V] << endl;
}