前言
背包系列是dd_engi大神在总结《解动态规划题的基本思考方式》时所写作的系列，用一系列背包问题，由浅入深，层层递进地讲解了动态规划的思考方式及其精髓所在，同时，如何举一反三，也是程序员所需的素养之一
由于网上有较多关于该系列的资料以及作者本人的文章都可以下载，所以这篇博客主要写我自己的心得体会和总结，而不再赘述细节
DPのKey Point
看了覃超的算法课，有新的感悟，在此总结一下
覃超指出，DP的关键在于两点：
- 定义DP数组
- 构造DP方程
如何定义数组也很重要，通常从最后的状态向前考虑，也可以从最开始的状态向后考虑，我个人认为后者较难，但是比较符合DP的思想。
至于DP方程，就是下文红字标出的，第i步与第i-1步的关系，只要数组定义好了，这一步不难
另外，关于DP和递归（回溯），贪心的关系：
- 递归+记忆化 == DP，递归是自顶向下，DP是自底向上，但是我认为思想很相像。区别于递归，DP的精髓在于能够存储局部最优解，避免了重复计算。同时，结合背包问题的做法，尽量减少DP数组的大小，最大重复利用，实在是妙！
- 贪心：每一步最大化，能获得最终解的一部分；但是DP没到达终点的话获取不到最终解的成分
第一讲 01背包问题
问题
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci，得到的价值是 Wi。求解将哪些物品装入背包可使价值总和最大。
基本思路
暴力破解（搜索方法）就不说了，时间复杂度为\(O(2^n)\)，即便用剪枝法裁掉一些，总体的耗时也是不能接受的
因此要考虑如何降低时间复杂度，最重要的是从最终的状态 i 开始，要想到 i 和 i-1 状态的局部关系，即DP方程，这里假设第i个物品使得背包价值最大，可以得到 \(F[i,v]=max\{F[i-1,v],F[i-1,v-C_i]+W_i\}\) 其中F[i,v]表示表示前i件物品放入V大小的背包里，能获得的最大价值 如果仅根据上述等式实现代码：
- 时间复杂度：\(O(VN)\)，V为背包容量，N为物品数量
- 空间复杂度：\(O(VN)\)
时间复杂度是没法降低了，但是空间复杂度可以巧妙降低，其实用 V 大小的数组记录 F 即可，还是看上述公式，注意，当更新 F[i,v] 时，其实要比较 F[i-1,v] 和 F[i-1,v-Ci] 的大小，在记录 F[i,v] 之前，F[v] 就代表的是 F[i,v]，假如我们能保证 F[v-Ci] 的值也是 F[i-1,v-Ci] 不就可以了吗？因此更新 F 时遍历的顺序需要从 V → cost，cost代表 Ci ，因为如果 V 比 Ci 小，都不够减了，显然不用更新，因此实现伪码(python style)如下
for i in 1 to N:
for v in V to cost:
f[v] = max(f[v], f[v-c[i]]+w[i])
- 空间复杂度：\(O(V)\)
过程ZeroOnePack,表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品 的费用和价值。
ZeroOnePack(cost, weight)
for v in V to cost
do f[v]=max(f[v], f[v-cost]+weight)
主体循环：
for i in 1 to N
do ZeroOnePack(c[i], w[i])
总结
01背包的动态规划解法是其他背包问题的基础和核心，就如上面红字标出的，核心就在于想到将复杂的问题分解为局部状态更新的重复过程，同时利用自底向上的方法，可以节省空间开销（斐波那契题的递归&动规）
第二讲 完全背包问题
问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
核心思路
先直接上伪码
CompletePack(cost, weight)
for v in cost to V
do f[v] = max(f[v], f[v-c[i]]+w[i])
发现区别了吗？区别在 v 的循环不是从 V to cost了，而是反之从 cost to V，原理如下：
- 其实DP的思想和01背包一样的
- 区别在于第i次循环的时候，第i件物品可以重复放，因此，之前更新 F[v] ，实际上是更新 i-1 的 F[v]，但是现在需要更新 i 本身的 F[v] ，因为 i 本身可以重复放置，因此这里选择从 cost to V，就可解决问题。
- 区别：01背包，更新的是 i-1 的 F[v] ；而完全背包更新的 i 本身的 F[v]
总结
看似很简单的变换，其实内涵完全不同，关键在于理解DP的局部变换步骤
第三讲 多重背包问题
问题
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
核心思想
将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值 均是原来的费用和价值乘以这个系数。使这些系数分别为\(1,2,4,...,2^{k-1},n[i]-2k+1\)，且k是满足\(n[i]-2k+1 > 0\)的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。 从而可以将实际复杂度从\(O(V × ∑n[i])\)缩减到\(O(V × ∑log n[i])\) 伪码如下
MultiplePack(cost, weight, amount)
if cost * amount > V:
then CompletePack(cost, weight)
return
int k = 1
while k < amount:
ZeroOnePack(k * cost, k * weight)
amount = amount - k
k *= 2
ZeroOnePack(amount * cost, amount * weight)
总结
没太多可说的，综合01背包和完全背包即可解决该问题，主要是乘以2倍系数的trick，可以多加应用
第四讲 混合三重背包问题
问题
问题如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？
核心思想
for i in 1 to N:
if i == 01背包:
ZeroOnePack(c[i], w[i])
elif i == 完全背包:
CompletePack(c[i], w[i])
else:
MultiplePack(c[i], w[i])
总结
综合利用之前问题解答即可
第五讲 二维费用的背包问题
问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。
核心思想
\[f[i][v][u] = Max \begin{cases} f[i-1][v][u] \\ f[i-1][v-a[i]][u-b[i]] + w[i] \end{cases}\]如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了，相信有了前面的基础，你能够自己实现出这个问题的程序。
总结
综合利用之前问题解答即可
第六讲 分组的背包问题
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
核心思想
for 所有的组k:
for v in V to 0:
for i in 组k:
F[v] = max(f[v], f[v-c[i]]+w[i])
即对一个组里的元素更新即可，因为组内元素互斥
总结
对组内物品多一层循环
第七讲 有依赖的背包问题
问题
ver1
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
ver2
更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集 合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一 个物品（只有一个主件）且不出现循环依赖。
核心思想
ver1
对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应 的最大价值F[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费 用为c[i]+k的物品的价值为F[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通 过一次01背包后，将主件i转化为V-c[i]+1个物品的物品组，就可以直接应用P06的算法解决问题 了。
ver2
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是， 由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件 也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合 所对应的附件组中各个费用的附件所对应的价值。
总结
对于依赖的附属集合，需要将其转换为之前的问题（01背包或者分组背包），从而解决问题。
Key：将复杂问题转换为已知问题
第八讲 泛化物品
问题
考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。
更严格的定义是，在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的 函数h，当分配给它的费用为v时，能得到的价值就是h(v)。
核心思想
泛化物品的和
如果面对两个泛化物品h和l，最大的价值为
\[f(v)=max\{h(k)+l(v-k)\}\quad 0\leq k \leq v\]由此可以定义泛化物品的和：h、l都是泛化物品，若泛化物品f满足以上关系式，则称f是h与l的 和。这个运算的时间复杂度取决于背包的容量，是\(Θ(V^2)\)。 综上所述，一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化 物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。
总结
求某个泛化物品的和(sum)，从而代表这个泛化物品的最大值
第九讲 背包问题问法的变化
问题
-
输出方案
解法：添加一个二维容器G[i][v]，存储路径
-
输出字典序最小的最优方案：这里“字典序最小”的意思是1..N号物品的选择方案排列出来以后字典序最小。以输出01背包最小字典序的方案为例。
解法：一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略。首先，子问题的定义要略改一些。我们注意到，如果存在一个选了物品1的最优方案，那么答案一定包含物品1，原问题转化为一个背包容量为v-c[1]，物品为2..N的子问题。反之，如果答案不包含物品1，则转化成背包容量仍为V，物品为2..N的子问题。不管答案怎样，子问题的物品都是以i..N而非前所述的1..i的形式来定义的，所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把物品逆序排列一下，以下按物品已被逆序排列来叙述。
在这种情况下，可以按照前面经典的状态转移方程来求值，只是输出方案的时候要注意：从N到1输入时，如果\(f[i][v] == f[i-1][i-v]\)及\(f[i][v] == f[i-1][f-c[i]] + w[i]\)同时成立，应该按照后者（即选择了物品i）来输出方案。
-
求方案总数
解法：只需将状态转移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，转移方程即为
\[f[i][v] = sum\{f[i-1][v],f[i][v-c[i]]\}\] -
最优方案的总数
解法：
for i in 1 to N: for v in 0 to V: f[i][v] = max(f[i-1][v],f[i-1][v-c[i]]+w[i]) g[i][v] = 0 if f[i][v] == f[i-1][v]: g[i][v] = g[i][v] + g[i-1][v] if f[i][v] == f[i-1][v-c[i]]+w[i]: g[i][v] = g[i][v] + g[i-1][c-v[i]] -
求次优解、第K优解
解法：其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。这里仍然以01背包为例讲解一下。
首先看01背包求最优解的状态转移方程：\(f[i][v] = max{f[i-1][v], f[i-1][v-c[i]] + wi]}\)。如果要求第K优解，那么状态f[i][v]就应该是一个大小为K的数组f[i][v][1..K]。其中f[i][v][k]表示前i个物品、背包大小为v时，第k优解的值。“f[i][v]是一个大小为K的数组”这一句，熟悉C语言的同学可能比较好理解，或者也可以简单地理解为在原来的方程中加了一维。显然f[i][v][1..K]这K个数是由大到小排列的，所以我们把它认为是一个有序队列。
然后原方程就可以解释为：f[i][v]这个有序队列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]这两个有序队列合并得到的。有序队列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]则理解为在f[i-1][v-c[i]][1..K]的每个数上加上w[i]后得到的有序队列。合并这两个有序队列并将结果的前K项储存到f[i][v][1..K]中的复杂度是O(K)。最后的答案是f[N][V][K]。总的复杂度是\(Θ(VNK)\)。
总结
背包问题的精髓在于如何构造局部循环，例如第i个物品与第i-1个问题的关系，大问题化简成小问题，降低问题复杂度，这也是动态规划（DP）的精髓所在了。
更多
个人更多算法总结在Github
