背包问题

01背包

引题：

原版： 有一个背包，可容纳重量为 $k$ 的物品。有 $n$ 个物品（每个物品只有一个），第 $i$ 个物品的重量为 $w[i]$，价值为 $val[i]$。求背包可容纳物品的最大价值。

魔改版：

你有 $n$ 项作业，但是你只有 $k$ 的时间，第 $i$ 项作业需 $val_i$ 个小时完成。但是，因为作业的内容、难度不同，对于每一项作业老师取得的快乐值也不同。

比如：如果你完成了一道全班只有你才完成的数学难题，老师会很高兴，即使你没有把定义练习抄写1000000000遍，老师也不会批评你；然而，如果你只把 $1+1=2$ 这类的题做完了，而稍微难一点儿的题就不做，老师就会很生气，认为你很懒，而让你把定义再抄100000000000遍。

问，在有限的时间内，如何使老师获得的快乐值最大？从而免去抄写

心灵的震撼

我相信，每一个第一次接触dp的人都会为之而着迷，毕竟一种优美的暴力手段是每一个有着 $ak\space IOI$ 的人所梦寐以求的。

dp之所以比暴搜快，可以看做是因为记录了中间过程的权值，进而优化掉了DFS中很多重复的子树，也可以看做一种牺牲空间换取时间的做法。

dp的核心思想就是从之前的状态推导当前状，进而在 $O(1\sim n)$ 的时间内找到当前状态的解。

也就是说，dp时无需考虑问题整体，而是化为一个个的状态，只需要关注某个状态如何从之前已经得到的状态中转移过来。

使用dp时很多时候论证其正确性是一个费时费力还费脑子的工作，因此dp题目需要你有一定的经验、大胆的尝试和欧气(毕竟dp的样例一般都很水，可能一道题样例全过就得个 $30+$ 的分数也不是没有可能)，因为考试的时候没那么多时间，大多数dp代码都不长，建议有想法就直接写，搞出来后跑样例，然后再做调整。正常情况下，只要能过 $1+$ 个样例，基本上不会暴零。可以先写出一个局部解，然后再完善dp的状态转移方程。

上面唠唠叨叨

dp最重要的就是状态和转移。

在01背包中，我们用 $dp[i][j]$ 表示在前 $i$ 件物品中选择，背包容量为 $j$ 时能装的最大价值。

然后，思考这个式子： $$ dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+val[i]) $$ $max$ 表示求取的最大值。因为我们已经知道了前 $i-1$ 个物品在背包容量为 $a\in[1,k]$ 时能装下的最大价值，因此对于第 $i$ 件物品，只有两种选择：

1. 装(前提是 $w[i]\le j$，毕竟得能装下才有讨论的必要)
2. 不装 (你能把我怎样？)

若不选择第 $i$ 件物品，很简单，其在容量为 $j$ 的背包下最大价值 $=$ 从前 $i-1$ 件中选择的最大价值(反正不选第 $i$ 件，所以没有影响) $=\space dp[i-1][j]$。

若选择第 $i$ 件物品，则应在前 $i-1$ 个中选择后至少剩余 $w[i]$ 的背包空间，然后选择第 $i$ 个物品，我们就会获得它的价值 $val[i]$，因此总共获得价值为 $dp[i-1][j-w[i]]+val[i]$。

易证，当物品相同时，大容量的背包装的总价值一定不小于小背包装的，因此只考虑最大的可能背包即可，不必遍历小背包。

当我们把这张表填完的时候，$dp[n][k]$ (表示选择前 $n$ 个物品背包容量为 $k$ 时能装下的最大值)就是我们要求的最终答案。

线性优化

我们发现了一个问题，上述01背包问题求解时，时间复杂度为 $O(nk)$，而空间复杂度也为 $O(nk)$。

因为这玩意常数比较小，在 $nk\le10^8$ 内都能跑过，但是，内存肯定不够用啊……人间疑惑

可不可以优化一下啊，毕竟好不容易不TLE了要是再MLE可就要砸电脑了螺旋升天了，进而怀疑人生……

好消息！好消息！好消息！空间可以优化！

观察转移方程，我们实际上只用到了 $2\times k$ 个值，其余的我们都不需要，所以，我们搞一个 int dp[2][k]好吗？

当然可以！只要你调的出来，理论上确实可行，只要你不是每搞完一行整一个 O(k) 的复制就行

下面，让我们再动脑子想一想，在缩小一下转移方程使用到的值，其实只有 $dp[i-1][a\in[1,j]]$，大于 $j$ 的我们用不到！

所以，我们能不能在一维数组上解决这个问题呢？

当然可以！没得怕的

只要我们从后往前遍历即可！即for(int i = k;i > 0;i--)即可。

因为，当我们遍历原二维数组第 $i$ 行时，现在数组中存储的就是原二维数组第 $i-1$ 行的值，并且即使大于 $j$ 的部分被更改，我们需要使用的小于等于$j$ 的部分仍旧是原第 $i-1$ 行的dp值，因此，状态转移方程魔改一下： $$ dp[j]=max(dp[j],dp[j-w[i]]+val[i]) $$ 体会到了人类脑洞之大

我们的最终答案，就在跑完之后，存在 $dp[k]$ 的地方。

注：

• 如果要 $dp[j] =$ 重量恰好为 $j$ 的最大价值，在DP前将 $dp$ 数组初始化为 $\infty$ 即可。
• 如果有重量为负值（显然此时要求的是重量恰好为 $j$ 的最大价值），循环顺序要改为正序，且 $dp$ 的下标统一加一个足够大的数以保证全为正数！
• 一维优化不能重构路径，但是二维数组可以通过一些办法(回溯，又称为逆推)求出咋装的。

完全背包

背包问题大多是从01背包的基础上演化而来，简言之就是01背包的增强版。

01背包的问题魔改一下就是完全背包：

我们还有一个背包，可容纳重量为 $k$ 的物品。有 $n$ 种物品（每种物品有无限多个），第 $i$ 种物品的重量为 $w[i]$，价值为 $val[i]$。求背包可容纳物品的最大价值。

我们依然使用 $dp[i][j]$ 表示从前 $i$ 种物品中选择，背包容量为 $j$ 时能装的最大价值。

然后，状态转移方程就变化了： $$ dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+val[i]) $$ 不难发现，对于第 $i$ 种物品，我们可以选择 $a\in[0,\frac{j}{w[i]}]$ 个。分为两类：

1. 不选第 $i$ 种物品。
2. 选第 $i$ 种物品 $a$ 个。

然后，这个问题又可以分为两步：

1. 确定选还是不选
2. 如果选，选几个

这时候，想一想dp的奥妙，即从已知推导出未知。

不选很好解决，$dp[i-1][j]$ 就是不选第 $i$ 种的最大价值。

那如果选呢？再回想dp数组的意义和01背包对于选物品的空间预留，可以得到 $dp[i][j-w[i]]+val[i]$ 这样的一个式子。我们只需要在可以选择第 $i$ 种的情况下留出 $w[i]$ 的空间来再装下一个第 $i$ 种物品即可。这样，我们无需知道第 $i$ 种物品应该选择几个，因为我们只需要在之前的最优解上进行状态转移即可，换言之我们只需要考虑多装一个是否更优，而不是遍历装几个更优，因为背包容量从小到大，能装下的个数也是从小到大。

线性优化

和01背包一样，完全背包依旧时间复杂度 $O(nk)$，空间复杂度 $O(nk)$。

那么，就会出现同样的问题。

既然差不多，完全背包也能线性优化吗？

**当然可以！**只不过需要进行一些调整，来适应新的状态转移方程。

我们发现，新的状态转移方程依赖于 $dp[i][a\in[0,j]]$ 而并不依赖于 $dp[i-1][a\in[0,k]]$ 和 $dp[i][a\in(j,k]]$，因此，我们需要改变遍历的顺序。

上面我们已经理解了线性优化后 $dp[j]$ 在修改前表示 $dp[i-1][j]$，所以for(int i = 0;i < k;i++)改为正序遍历即可先求出第 $i$ 行较小的 $j$ 进而推导出较大的 $j$，完成dp。这样，空间复杂度降为 $O(k)$。

同01背包，一维优化不能重构路径，但二维可以。

多重背包

同样，上来还是老问题：

我们又有一个背包，可容纳重量为 $k$ 的物品。有 $n$ 中物品，第 $i$ 种物品有 $c[i]$个，每个重量为 $w[i]$，价值为 $val[i]$。求背包可容纳物品的最大价值。

看，看，看，是不是和01背包又是差不多？

所以，最简单的想法就是将每个物品拆成独立的个体，跑01背包，时间复杂度为 $O(k\times\sum_{i=1}^nc[i])$。

但是，显然，太慢了！

观察，多重背包与01背包最大的不同，就是有多个物品属性相同， 这也成为优化的入手点。

先说一个题外话：人民币大家都知道吧，有$1$元的、$10$元的还有红色毛爷爷……那么，为什么不全用$1$元的？这样也可以表示任意的金额啊？

但是，前几天刚出现了一个新闻，某男子用一麻袋硬币交房租被告上法庭……所以，体会到了红色毛爷爷的重要性。

因此，我们的多重背包也可以借助这个思想，将 $c[i]$ 个物品划分成几组，从而能且仅能表示出所有 $a\in[0,c[i]]$ 。

问题来了，知道了为什么要分组，接下来就是怎么分组了。

二进制拆分

我们先来看 $0\sim19$ 的二进制表：

十进制	二进制
0	00000
1	00001
2	00010
3	00011
4	00100
5	00101
6	00110
7	00111
8	01000
9	01001
10	01010
11	01011
12	01100
13	01101
14	01110
15	01111
16	10000
17	10001
18	10010
19	10011

然后，我们发现，对于任意一个二进制数，均可以用不同的只有一位是 $1$ 的二进制数相加得到，如：

$13$ = $(01101)_2$ = $(01000)_2+(00100)_2+(00001)_2$

而这个规律翻译成十进制就是，对于数 $2^{k-1}<a\le2^k$ 一定可以用 $2^0,2^1,2^2,2^3,\dots,2^{k-1}$ 和 $a-2^{k-1}$ 中的某几个数相加得到。这就构成了我们分组的依据。

我们将 $c[i]$ 拆分成 $2^0,2^1,2^2,\dots,2^{k-1},c[i]-a$，当成一共 $k$ 个物品，第 $x$ 组(个)物品的重量为 $第x组的个数\times w[x]$，价值为 $第x组的个数\times val[x]$。

这样拆分之后，在跑01背包，即可将时间复杂度降至 $O(k\times\sum_{i=1}^n\log{c[i]})$。

混合背包

01、完全、多重背包三合一。大锅炖

01背包当 $c[i]=1$，完全背包当 $c[i]=\lfloor\frac{k}{w[i]}\rfloor$ 即可。

多限制背包

物品有更多属性，对每种属性都有限制。

把所有限制都加到状态里即可。

分组背包

描述：有n件物品，分为若干组，现约束，在每组物品里最多取一件物品放入背包，每件物品的重量确定，价值确定，背包容量确定，求在不超过背包容量的情况下，可以存放的最大价值。

$w[i][j]$ 表示第 $i$ 组第 $j$ 件物品的重量，$val[i][j]$ 表示第 $i$ 组第 $j$ 件物品的价值，$dp[a][b]$ 表示在前 $a$ 组中选择重量不大于 $b$ 的最大价值。

对于任意一组物品，共计两类状态：

1. 一个都不选
2. 选择第 $i\in[1,len]$ 个

因此，在01背包的基础上进行嵌套循环，每次遍历整组，求出最优解即可。

线性空间优化见上文。

背包方案计数

把所有的取 $max$ 都改成求和即可。

注意：多重背包不能用二进制拆分优化了，因为同样的数量拆分方式不唯一。

依赖性背包

依赖关系只有一层：把每个“主件”当做一个背包，然后将各背包合并（也是树形背包的基本思路）。

无循环依赖（树形背包）：树形DP。

有循环依赖：Tarjan+缩点 + 树形DP。

请在相应章节查看。