基础的三类背包（01，完全，多重）的滚动数组优化原理以及时间优化，分组背包，有依赖的背包，树上背包，背包方案。

[TOC]

背包dp

背包类问题是一种有限制的选择问题，最后一般要最大或者最小化某个指标，或者单纯只是计数。

下面先把三种简单的背包问题的滚动数组，循环顺序等实现上的细节讲明白，再考虑二进制以及单调队列等时间优化，最后介绍其他各类背包问题。

大部分篇幅是老文了，小部分是新加的。

01背包

每种物品要么选择，要么不选择，期望最后总价值最大。

最基础解法

设dp[i][j]为从前i个物品中选，至多选择物品总体积为j的方案集合中的所能得到的最大价值。

处理过程为：

dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= v[i]) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
}
cout << dp[n][m] << endl;

可以画一下网格图，模拟一下循环，会发现dp过程中，dp[i][j]用到的结果只是dp[][]数组的上一行。也就是说，递推过程中只用到了上一行这一行的计算结果，再往前的结果就没用了，所以不加任何优化的01背包枚举顺序不会影响结果。

滚动数组优化及其带来的问题

如果省略dp的阶段维度，使用滚动数组优化01背包的空间：

dp[0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}
cout << dp[m] << endl;

那么，由于只保留了一维数组，这个数组在dp进行过程中，一部分是第i阶段的结果，一部分是第i - 1阶段的结果，为了保证我们总是使用第i - 1阶段的结果去更新第i段的结果，所以我们必须保证先更新右边的，再更新左边的，所以必须从大到小枚举体积。

有一些01背包的变种问题，比如3417. 砝码称重 - AcWing题库，该题状态转移的时候，dp[i][j]和dp[i - 1][j + v]以及dp[i - 1][j - v]还有dp[i - 1][j]都有关系，所以这个就不能原地做背包，至少要开两个数组，在dp开始之前先把上一个阶段的结果存到临时数组中，然后计算当前阶段，最后把当前阶段的结果拷贝到那个数组中，才可以实现空间优化。

稍有不同的状态定义的方式以及带来的问题

有一种状态定义的方法是：设dp[i][j]为从前i个物品中选，体积恰好为j的方案集合中最大的价值。该状态定义和前面提到的状态定义的最大的不同就在于，恰好背包的状态不一定都是合法状态，但是前面的至多背包必然至少包含一个合法方案（什么都不选，不需要空间），这就导致前面的背包初始化全部为0，而恰好背包除了dp[0][0] = 0，其他的必须显式初始化为-INF，否则会出现非法状态刷新合法状态的错误。最后统计答案的时候，恰好背包必须遍历整个状态空间，找到所有合法状态，才能知道哪个是最优解。

在一些基于01背包的问题中，有时候除了最大价值还要我们统计一些其他信息，这个时候使用恰好背包的状态定义方式会更方便。

还有一种状态定义方式，适用于需要选择至少达到某个指标的的物品的问题，可以形象地理解为至少背包。这种问题一般是设dp[i][j]代表从前i个物品中选，使得指标至少达到j的所有方案组成的集合的某个属性（xx最大/最小）

至少背包的例题可以参考这一道：潜水员

以这个问题为例子，我们分析一下这种状态定义下的初始化，转移以及最后答案的组成：

• 先不使用滚动数组，设dp[i][j][k]代表从前i个气缸中选，氧气至少是j，氮气至少是k的气缸的最低重量。

• 对于初始化

  • 考虑dp[0][0][0]，代表从前0个气缸中取，两种气体都至少是0，那么显然最低重量就是不选，所以初始化成0就好了
  • 考虑dp[i][0][0]，i > 0，显然最优方案也是不选，所以也初始化成0
  • 其他的dp[i][j][k]，由于要求最小值，所以初始化成无穷大。

• 对于转移

  • dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - a[i]][k - b[i]] + c[i])
  • 这里就有了一个很有意思的问题，考虑负数状态dp[i][-1][-2]，虽然下标出现负数会导致意想不到的后果，但是这个状态本身确实是合法的：至少是-1的话，0也是至少-1，2也是至少-1，所以这个状态里面可以有合法的方案。所以在转移的时候，枚举j < a[i], k < b[i]的状态是可以的。但是我们的代码中还是不可以出现负数呀，这里可以使用一个小技巧：由于至少是-1有意义的前提是其中有至少为0的方案，所以我们发现需要用到至少为某个负数的方案时，直接使用至少为0的就好了。
  • 综上，在循环的时候，可以把各项限制循环到0；在转移过程中，出现的负数状态全部用0状态替换就好了。

• 对于答案

  • 很显然了，因为状态定义和问题描述的形式一毛一样，所以直接就是最后一个状态。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int V1 = 25, V2 = 85, N = 1010;

typedef long long ll;

ll dp[V1][V2], n, v1, v2, a[N], b[N], c[N];

int main() {
    cin >> v1 >> v2 >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = v1; j >= 0; j--) {
            for (int k = v2; k >= 0; k--) {
                dp[j][k] = min(dp[j][k],
                               dp[max(0ll, j - a[i])][max(0ll, k - b[i])] + c[i]);
            }
        }
    }
    
    cout << dp[v1][v2] << endl;
    
    return 0;
}

至此，01背包的原理上的疑点已经全部解决了。

完全背包

完全背包问题中，所有物品可以选择任意数量，只要满足体积限制即可。

最基础解法

状态表示采用至多背包，则朴素解法是：

考虑dp[i][j]，其可能由dp[i - 1][j] dp[i - 1][j - v[i]] dp[i - 1][j - 2 * v[i]] ... dp[i - 1][j - s * v[i]]转移过来，其中s = j / v[i]（这一点很重要）。

空间的话，由于只和上一行的左边有关系，所以可以原地使用滚动数组优化。

时间复杂度的优化

这个玩意看起来需要枚举转移，但是实际上我们可以发现一定的规律：考虑dp[i][j]和dp[i][j - v[i]]之间的关系，会发现dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])，这个关系可以通过展开二者的计算表达式发现。注意到dp[i - 1][j]是老的值，但是在dp[i][j]的上一行正上方，dp[i][j - v[i]]是该阶段的新值，且**j - v[i] < j（即需要使用左边的新状态），所以，我们在算完全背包的时候，如果按照从小到大**的顺序枚举体积维度，那么只要两重循环就可以搞定，把滚动数组也加上就是：

dp[0] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }
}
cout << dp[m] << endl;

这个优化非常重要，在最基础的dp的优化中，可以通过观察刷新新状态所需要的老状态之间的关系，来借用一些已经存在的结果进行计算，优化复杂度。最常见的老状态之间的关系就是可以从某一个以较小的复杂度（比如$O(1)$）转移到另一个状态。

由于最大的个数都是枚举到j / v[i]，所以才能用dp[i][j - v[i]] + w[i]代替后面那一串。

多重背包

每个物品给出可供选择的数量s[i]，总体积不能超过限制。

最基础的解法

仍然按照至多背包的状态设计。考虑状态转移，最朴素的转移方法是，考虑使用dp[i - 1][j], dp[i - 1][j - v[i]] + w[i], dp[i - 1][j - 2 * v[i]] + 2 * w[i] ... dp[i - 1][j - s[i]*v[i]] + s[i] * w[i]来更新dp[i][j]。

先循环谁

在不做任何优化的情况下，由于状态表示中引入了阶段这个维度，且由转移方程可以发现**i阶段只由i - 1阶段转移过来**，所以无论先枚举体积还是先枚举个数，无论是从小到大还是从大到小枚举，都不会对结果产生影响。

万恶之源在于优化，没错说的就是你滚动数组，此处特指原地滚动数组。使用滚动数组之后，一定要注意原转移方程中当前状态是那些阶段的状态转移过来的，以此确定到底采用怎样的枚举顺序来保证既原地修改又使用正确的值转移。注意到dp[i][j]由其上一行的左半部分转移过来，所以理论上应该从大到小枚举体积，并且，**每次体积自减时，一定要保证这个时候这个体积的答案已经完全算完了！**所以，枚举选择几个的循环，应该放到枚举体积的循环里面，至于从大到小还是从小到大，倒是没有什么特别的要求了。

以上，便是不对时间进行优化的情况下多重背包中值得注意的一些问题。

二进制拆分优化

二进制优化的原理在于，考虑将s[i]分解成$2^0+2^1+2^2+...+2^p+q=s[i]$ ，这是p + 2种物品，不管我们取0到s[i]中的哪个数目，这p + 2个物品都能拼凑出这种方案，且是以01背包的方式。倘若把所有的物品都做二进制拆分，那么只要做01背包就能解决问题了，复杂度为$O(V\sum_{i = 1}^n \log s[i])$ ，已经是一个很大的优化了。

为何如此拆分物品

有人说，为何要如此二进制拆分？直接把二进制位中不是0的那些取出来作为物品不好吗？下面我们将分别解答这些疑问。

先说后者，假如有一个数是11，其二进制表示为1011，如果只拆成1000，10，1，那么0100这种情况就凑不出来，所以并不是随便一个二进制拆分就能保证计算的正确性的。那么为啥上面提到的二进制拆分就可以呢？考虑式子$2^0+2^1+2^2+...+2^p+q=s[i]$，显然，左边的p + 2个物品一定能无压力地通过01背包组合出$0$到$2^{p + 1} - 1$，那么$2^{p + 1}$到$s[i]$之间的这些数呐？如果必选$q$的话，加上前面那些，那么可以无压力通过01背包组合出$q$到$2^{p + 1} + q - 1$之间的数，而$2^{p + 1} + q - 1 = s[i]$，所以$0$到$s[i]$之间的任何数（包括边界）都可以被这p + 2个物品通过01背包的规则组合出来，所以这种拆分是可以保证正确性的。

拆分物品的时机

分两类，一类是读入的时候就显式拆分物品，另一类是dp过程中模拟拆分物品。前者的易错点都被后者包含了，所以我们只谈一谈dp过程中模拟拆分物品应该注意的地方。

首先，考虑朴素情况下加滚动数组的解法，那个时候要求我们从大到小循环体积，并且选择物品的个数应该放到最内层进行枚举。由于现在我们做了拆分之后就是在做01背包，所以每个拆分之后的物品理论上应该作为dp中的一个阶段，只有本阶段算完了，才能算下一个阶段，所以应该先拆分好，再枚举体积做01背包，绝对不能先枚举体积再拆分物品，这样算下去动态规划的阶段就不对了。

代码模板：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 2020;

typedef long long ll;

ll dp[M], n, m, v[N], w[N], s[N];

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

单调队列优化

一般地，可以使用单调队列优化的dp问题具有下面的特点：

• 决策取值的上下界随着阶段的进行而单调变化
• 每个决策在候选集合中被插入和删除都至多一次

我们来看一下多重背包问题为什么具有这种特点。

这里，我们假设背包容量足够大，以至于对于物品i来说，把全部的c[i]个都放进去都不至于超过容量。

那么我们可以发现如下关系：

dp[i] = max(dp[i], dp[i - v[i]] + w[i], dp[i - 2 * v[i]] + 2 * w[i], ..., dp[i - c[i] * v[i]] + c[i] * w[i]);

dp[i - v[i]] = max(dp[i - 2 * v[i]] + w[i], dp[i - 3 * v[i]] + 2 * w[i], ..., dp[i - (c[i] + 1) * v[i]] + c[i] * w[i]);

可以注意到，dp[i]和dp[i - v[i]]的转移方程中，若不考虑w[i]的偏移，那么可以转移到dp[i]的状态和可以转移到dp[i - v[i]]的状态刚好是多一个和少一个的关系：dp[i]比dp[i - v[i]]多一个前驱dp[i - v[i]]，少一个前驱dp[i - (c[i] + 1) * v[i]] ，且对于任意的dp[i - c * v[i]]， 1 <= c <= c[i]，随着c的改变，决策的上下界是单调改变的，所以这个式子的计算是可以用单调队列来优化的。

但是注意到，如果是顺序枚举容量，那么枚举完j之后是j + 1或者j - 1，不是j + v[i]或者j - v[i]，而j + 1和j - 1与j的决策集合甚至可能没有交集，这应该如何处理？注意到j , j - v[i], j - 2 * v[i], ... j - c[i] * v[i]对v[i]的余数相同，故可以按照余数0到v[i] - 1来分类，先枚举余数，再枚举转移，这样同一余数的状态就可以按照相邻的顺序被枚举到了。

代码模板如下，细节都在代码中注释了：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 20020;

typedef long long ll;

ll dp[M], n, m, q[M], v[N], w[N], c[N];

ll f(int u, int i, int k) {
    return dp[u + k * v[i]] - k * w[i]; 
}

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> c[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int u = 0; u < v[i]; u++) {
            int l = 1, r = 0;
            int maxp = (m - u) / v[i];
            
            // 第一个要计算的是体积最大的状态
            // 所以需要先往单调队列里面插入一些东西
            // dp[u + p * v[i] = max(dp[u + k * v[i]] + (p - k) * w[i])  p - c[i] <= k <= p - 1
            // 同类项合并一下
            // dp[u + p * v[i]] = max(dp[u + k * v[i]] - k * w[i] + p * w[i]) 
            // 由于最内层枚举的是k，所以维护的其实是关于f(k)的一个单调队列
            // f(k) = dp[u + k * v[i]] - k * w[i] 
            // 不要越界
            for (int j = maxp - 1; j >= max(0ll, maxp - c[i]); j--) {
                while (l <= r && f(u, i, q[r]) < f(u, i, j)) {
                    r--;
                }
                q[++r] = j;
            }
            
            // 从大到小枚举体积，进行状态转移
            for (int p = maxp; p >= 0; p--) {
                // 排除过期的状态
                while (l <= r && q[l] > p - 1) {
                    l++;
                }
                // 状态转移
                if (l <= r)
                    dp[u + p * v[i]] = max(dp[u + p * v[i]], f(u, i, q[l]) + p * w[i]);
                // 插入新的决策并维护单调性
                if (p - c[i] - 1 >= 0) {
                    while (l <= r && f(u, i, q[r]) < f(u, i, p - c[i] - 1)) {
                        r--;
                    }
                    q[++r] = p - c[i] - 1;
                }
            }
        }
    }
    
    cout << dp[m] << endl;
    
    return 0;
}

至此，最基础的三种背包问题的疑问就全部解决了。

混合背包

上面三种背包混起来，当成多重背包处理一下即可。

多维费用背包

需要注意到底有几个限制条件，每种限制条件都应该是dp状态中的一部分。

没啥好说的，把状态维度多加点以表示不同的限制，循环多几层就好了。

分组背包

同组内的物品只能选择一个，求满足条件下的最大价值。

循环时枚举顺序的确定：

• 一种理解思路是先阶段，再状态，最后决策，所以应该先枚举物品组，再枚举容量，最后枚举组内物品。
• 另一种理解思路是假设枚举组之后直接枚举组内物品，最后枚举容量，那不就成了01背包了嘛，所以还是得先枚举容量。

代码模板：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int dp[N], n, m, t, s, v[N], w[N];

int main() {
    cin >> n >> m;
    
    // 枚举物品组
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= s; j++) {
            cin >> v[j] >> w[j];
        }
        
        // 枚举状态
        for (int j = m; j >= 0; j--) {
            // 枚举决策
            for (int k = 1; k <= s; k++) {
                if (j >= v[k]) {
                    dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
                }
            }
        }
    }
    
    cout << dp[m] << endl;
    return 0;
}

扩展问题可能有每个物品组中可以拿不同数量的物品。这时候可以设计给每一组设计一个虚物品，必选，然后虚物品是其他所有物品的父亲，这样就转化成了树上背包/有依赖的背包问题。

对于比较简单的有依赖背包问题，可以转化成分组背包来做，比如 金明的预算方案 ：

本题中主件最多有2个附件，所以我们其实可以轻松地枚举出每个物品组的所有决策，即啥都不选或者选主件且二进制枚举其他附件的选法。如果题目的数据范围做出修改，每个主件可以有很多附件，那么二进制枚举会导致超时。这个时候可以考虑按照分配给这个物品组的体积来划分要计算的问题，这样每个组内的状态就会从指数降低到线性（$2^k$到$m + 1$，使用一个体积来表示一类选择方案）。

参考代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// 每个物品的价格以及关心的价值
typedef pair<ll, ll> PII;

const int N = 32010, M = 70;

PII master[N];
bool is_master[N];
vector<PII> annex[N];
ll n, m, dp[N];

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

    ll v, p, q, w;
    for (int i = 1; i <= n; i++) {
        cin >> v >> p >> q;
        if (q == 0) {
            is_master[i] = true;
            master[i] = {v, v * p};
        } else {
            annex[q].push_back({v, v * p});
        }
    }

    for (int i = 1; i <= n; i++) {
        if (is_master[i]) {
            for (int j = m; j >= 0; j--) {
                // 暴力枚举组内选法，类似于暴力做01背包
                for (int k = 0; k < (1 << annex[i].size()); k++) {
                    v = master[i].first, w = master[i].second;
                    for (int l = 0; l < 3; l++) {
                        if (((k >> l) & 1) != 0) {
                            v += annex[i][l].first;
                            w += annex[i][l].second;
                        }
                    }

                    if (j >= v) {
                     	dp[j] = max(dp[j], dp[j - v] + w);   
                    }
                }
            }
        }
    }

    cout << dp[m] << endl;

    return 0;
}

有依赖的背包/树上背包

物品之间存在一定的依赖关系，比如b依赖于a，那么可以单独买a，如果要买b则必须要购买a。一般来讲依赖关系组成一个森林。

对于简单的有依赖背包问题（比如金明的预算方案），可以通过枚举决策，将其简单地转化为分组背包问题。但对于依赖比较多的背包，就必须使用树上背包的思路成批计算了。这里和基于枚举所有决策的分组背包的区别就在于这里是每次刷新一类（占用体积为k的那类）决策的最大值。

代码实现的时候有很多细节需要注意。

参考代码模板：

void dfs(int u) {
    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        int son = edge[i].to;
        dfs(son);

        // 先只考虑子树，只是给树根留出位置
        // 这里之所以从大到小枚举体积，是因为实际上这里隐含着一个滚动数组
        // 每次我们都是用前x棵子树的结果，去刷新前x + 1棵子树的结果
        // 但是我们都是用dp[u]这一维来存储的
        // 所以这里确实压掉了一维（子节点）
        for (int j = m - v[u]; j >= 0; j--) {
            for (int k = 0; k <= j; k ++) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]);
            }
        }
    }

    // 把树根加进去，这里是强制加，所以强制刷新而不是取max
    for (int i = m; i >= v[u]; i--) {
        dp[u][i] = dp[u][i - v[u]] + w[u];
    }
    // 把不足以加入树根的结果清零
    for (int i = 0; i < v[u]; i++) {
        dp[u][i] = 0;
    }
}

背包方案

背包方案存在两个子问题：

• 背包最优方案计数
• 一个具体的最优方案

背包最优方案计数

只需要在维护dp[i][j]的同时，维护g[i][j]即可：

• 当dp值被刷新的时候，g值被覆盖；
• 当dp值和转移用到的值相等时，g累加。

一个代码实现如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

ll dp[N], g[N], n, m, v[N], w[N];

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

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

    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    g[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            if (dp[j] == dp[j - v[i]] + w[i]) {
                g[j] += g[j - v[i]];
            } else if (dp[j] < dp[j - v[i]] + w[i]) {
                g[j] = g[j - v[i]];
            }
            g[j] %= mod;
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    ll maxw = 0;
    for (int i = 0; i <= m; i++) {
        maxw = max(maxw, dp[i]);
    }

    ll res = 0;
    for (int i = 0; i <= m; i++) {
        if (maxw == dp[i]) {
            res += g[i];
            res %= mod;
        }
    }

    cout << res << endl;

    return 0;
}

背包求具体方案

一般对具体方案没有特殊要求。这个时候直接用mark[][]数组记录转移就好了。

如果有特殊要求，比如需要输出字典序最小的方案，则需要仔细设计一下应该如何转移。

正着循环物品来dp的话，由于最后的方案输出要从dp[n][m]往前递归，所以考虑的是能不能选n，能不能选n - 1，能不能选n - 2…能不能选1，显然这样考虑得到的不是字典序最小的。

如果最开始反着推去dp，那么最后从dp[1][m]递归，考虑的顺序就是能不能选1，能不能选2，能不能选3…能不能选n，这样得到的才是最小的字典序的方案。

在做mark标记的时候，反着dp的话，应该是能用当前物品就用当前物品。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

typedef long long ll;

ll dp[N][N], mark[N][N], n, m, v[N], w[N];

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

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

    for (int i = n; i > 0; i--) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j >= v[i]) {
                if (dp[i][j] <= dp[i + 1][j - v[i]] + w[i]) {
                    dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
                    mark[i][j] = 1;
                }
            }
        }
    }

    for (int i = 1, j = m; i <= n; i++) {
        if (mark[i][j] == 1) {
            j -= v[i];
            printf("%d ", i);
        }
    }

    return 0;
}

背包dp完结撒花！