背包问题及 LIS 优化

快一年没更新了，又是满血复活的一年一起加油进步！！！

目录

记忆化搜索转递推的方法

背包问题

01 背包问题

完全背包问题

多重背包问题

练习

LIS 的单调性优化

排列 LCS 的优化

练习

升级版（无题号）

题面

分析

---

记忆化搜索转递推的方法

在上一节课的讲解里，为了让大家更好地接受动态规划，我们采用了记忆化搜索的方法。但目前算法圈子里，大家还是习惯写递推版本的动态规划，因为它更简洁。下面给一个通用的方法，将记忆化搜索转为动态规划。

首先，对于记忆化搜索的终止状态赋值，就是动态规划中给初始状态赋值。例如，斐波那契数列搜索算法的终止条件是 if(n==0 || n == 1) return f[n] = 1; 在动态规划中就改写为 f[0] = f[1] = 1。

接着，有多少个参数就写多少个循环。观察搜索 状态参数是否单调变化 。比如对于斐波那契数列的搜索算法， nn 是单调递减的，此时改成动态规划时，就从小到大枚举 nn 。

最后，在循环里面，把记忆化搜索的主体部分原封不动地搬过来。把递归改成调用数组。

值得一提的是，并不是所有的记忆化搜索递归写法都能转写成递推的写法，比如上一节课的“滑雪、黑板上的数字”。只有当参数单调变化时，才适合转写成递推写法。

随着我们熟练度的提升，慢慢地，我们可以学会直接写出递推版的动态规划，其核心步骤如下：

• 设计出状态数组，确定其表达的状态
• 分析出状态转移方程
• 确定初始状态
• 确定目标状态
• 写出递推 DP 代码

背包问题

背包问题是动态规划中最为经典的一类问题。我们先来看其中最简单的 01 背包问题。

01 背包问题

P1417 01 背包：今有一个重量为 WW 的背包，你有 nn 个物品，其中第 ii 个物品的重量为 wiwi​ ，价值为 cici​ 。你希望选出其中的一些装入背包，使得他们的重量之和不超过 WW 的前提下价值最大。

n≤30,W≤200n≤30,W≤200

类似于上节课讲过的插花问题，我们发现如果我们确定是哪些物品装入背包，那么他们装入背包的顺序就无所谓了。这意味着，我们可以规定装入背包的物品是按编号从小到大的顺序装入的背包，这样好像就和插花问题一样了。

考虑最后一个物品，如果它要装入背包，那么背包容量仅剩 W−wnW−wn​ ，于是接下来的问题就变成了将前 n−1n−1 个物品装入容量为 W−wnW−wn​ 的背包，使其价值最大，这就是一个子问题。在这个最大价值的前提下，加上 cncn​ ，就能得到装入最后一个物品所对应的答案。那如果最后一个物品不装入呢？那背包的容量就还剩下 WW ，而物品只剩下前 n−1n−1 个了，问题就变成了前 n−1n−1 个物品装入容量为 WW 的背包的一个子问题。两者取 max⁡max ，就能得到我们最终想得到的答案。

那么我们发现，我们的子问题实际上是有两个参数，一个是背包剩余的容量，一个是前几个物品。我们可以用二维数组把包含这两个参数的答案保存下来。用 f[i][j]f[i][j] 表示前 ii 个物品，装入容量为 jj 的背包所得到的最大价值。得到递推方程：

f[i][j]=max⁡(f[i−1][j]（第i个物品不装）,f[i−1][j−wi]+ci（第i个物品装）)f[i][j]=max(f[i−1][j]（第i个物品不装）,f[i−1][j−wi​]+ci​（第i个物品装）)

注意，转移的后半段得以执行的条件是 j−wi≥0j−wi​≥0 ，如果 j−wi<0j−wi​<0 ，则后半段的转移是不合法的，状态转移方程也应该退化为 f[i][j]=f[i−1][j]f[i][j]=f[i−1][j] 。

采用记忆化搜索的方式可以实现上面问题的求解，但我更倾向于递推的方式。注意到 ii 在转移的时候是递减的，所以可以从小到大枚举 ii 。递推的写法如下：

for(int i=1; i<=n; i++){for(int j=0; j<=W; j++){f[i][j] = f[i-1][j];if(j >= w[i])f[i][j] = max(f[i][j],f[i-1][j-w[i]]+c[i]);}
}

时间复杂度为 O(nW)O(nW) 。至此我们解决了 01 背包问题。

思考：

我们知道使用动态规划的方法解决 01 背包问题的时候，时间复杂度为 O(nW)O(nW) 。有人认为，动态规划求解 01 背包是一个时间复杂度为指数级别的算法。你认为他的说法有道理吗？为什么？

我们再来考虑一下空间复杂度，解决 01 背包需要存下第一维为 nn ，第二维为 WW ，一共 nWnW 个信息，所以空间复杂度也为 O(nW)O(nW) 。空间复杂度可以优化吗？当然可以，我们发现更新 f[i]f[i] 的时候， f[i]f[i] 的信息只和 f[i−1]f[i−1] 这一维有关，所以对于前面的 f[i−2],f[i−3]…f[i−2],f[i−3]… ，我们就没必要保存了。所以我们只开一个第一维度大小为 2 的二维数组，根据 ii 的奇偶性，将奇数的 ii 存入 f[1]f[1] ，将偶数的 ii 存入 f[0]f[0] 实现更新，代码如下：

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

这样的空间复杂度为 O(W)O(W) ，实际上是 2W2W 。一般的题目都够用了（这也是动态规划优化空间的最通用的方法，适合观察能力一般的同学）。但有些题目对空间要求更苛刻，只允许你开 WW 的空间，怎么办呢？我们观察状态转移方程：

f[i][j]=max⁡(f[i−1][j],f[i−1][j−wi]+ci)f[i][j]=max(f[i−1][j],f[i−1][j−wi​]+ci​)

再想想我们的代码，我们的代码在循环里分为两步，第一步是把 f[i][j]f[i][j] 赋值成 f[i−1][j]f[i−1][j] ，第二步是利用 f[i−1][j−wi]f[i−1][j−wi​] 更新自己。那我们也可以换种做法，先用一重循环把所有的 f[i][j]f[i][j] 赋值成 f[i−1][j]f[i−1][j] ，再用一层倒着的循环，利用 f[i][j−wi]f[i][j−wi​] 更新 f[i][j]f[i][j] 。这里注意由于是用倒着的循环，所以更新 f[i][j]f[i][j] 的时候， f[i][j−wi]f[i][j−wi​] 还是等于 f[i−1][j−wi]f[i−1][j−wi​] 的，所以才可以这么做。

有了上面的思路之后，如果我们改用一维数组实现，那么第一重循环的赋值就是自动的，只需要额外执行第二重循环即可。

for(int i=1; i<=n; i++){for(int j=W; j>=w[i]; j--){f[j] = max(f[j], f[j-w[i]]+c[i]);}
}

完全背包问题

再来看另一类背包问题：

P2081 完全背包：今有一个重量为 WW 的背包，你有 nn 种物品，每种物品都有无限个，其中第 ii 种物品的重量为 wiwi​ ，价值为 cici​ 。你希望选出其中的一些装入背包，使得他们的重量之和不超过 WW 的前提下价值最大。

n≤1000,W≤10000n≤1000,W≤10000

这跟01背包问题一样有 O(VN)O(VN) 个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态 f[i][j]f[i][j] 的时间是 O(j/v[i])O(j/v[i]) ，总的V复杂度可以认为是 O(V∑(V/v[i]))O(V∑(V/v[i])) ，是比较大的。

f[i][j]=max⁡(f[i][j],f[i−1][j−k×w[i]]+k×c[i])f[i][j]=max(f[i][j],f[i−1][j−k×w[i]]+k×c[i])

上式可以看成是求 f[i−1][j−k×w[i]],k∈[0,m]f[i−1][j−k×w[i]],k∈[0,m] 这个序列的所有前缀的最大值，不过需要加一个偏移量 k×w[i]k×w[i] 。

将 01 背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明 01 背包问题的方程的确是很重要，可以推及其它类型的背包问题。

代码如下：

for(int i = 1; i <= n; i++)for(int j = 0; j <= W; j++)for(int k = 0; k*w[i] <= W; k++) {if(j >= k*w[i])f[i][j] = max(f[i][j], f[i-1][j-k*w[i]] + k*c[i]);}
cout << f[n][m];

上面的代码的时间复杂度是 O(W∑i=1nWw[i])O(W∑i=1n​w[i]W​) ，如果 WW 过大的话，还是会超时的，考虑优化。类似 01 背包，我们同样可以观察出来放物品的顺序和最后的价值无关，所以假设物品是按编号从小到大放入背包的。于是我们观察最后一种物品。

假设当前背包容量为 WW ，我们考虑最后一种物品，我们一个一个往里放。现在，我们假设往里放了一个最后一种物品，那么背包容量就变成了 W−wnW−wn​ ，我们还可不可能继续往里面放最后一种物品？可能，因为它有无数多个。所以问题是不是就变成了往容量 W−wnW−wn​ 的背包里，放前 nn 种物品，得到的最大价值。求解出这个，加上我们已经确定放进去的一个最后一种物品，就得到了容量为 WW 的背包往里放一个最后一种物品对应的答案。

那如果不往里放最后一种物品，那是不是可以假装没有最后一种物品了，背包容量还是 WW ，所以问题就是容量为 WW 的背包放前 n−1n−1 种物品得到的最大价值。也是一个子问题。

于是可以写出递推方程，用 f[i][j]f[i][j] 表示将前 ii 种物品放入容量为 jj 的背包：

f[i][j]=max⁡(f[i][j−w[i]]+c[i]（放一个）,f[i−1][j]（不放）)f[i][j]=max(f[i][j−w[i]]+c[i]（放一个）,f[i−1][j]（不放）)

时间复杂度也是 O(nW)O(nW) 。与 01 背包的代码仅有一处不同。

for(int i=1; i<=n; i++){for(int j=0; j<=W; j++){f[i][j] = f[i-1][j];if(j >= w[i])f[i][j] = max(f[i][j],f[i][j - w[i]] + c[i]);}
}

 

然后我们同样可以考虑空间优化。上面的代码同样可以改写为，先将 f[i][j]f[i][j] 赋值成 f[i−1][j]f[i−1][j] 以实现后面那种转移，再利用 f[i][j−w[i]]f[i][j−w[i]] 更新 f[i][j]f[i][j] 。注意这里第二维需要顺序枚举，因为顺序枚举的时候， f[j−w[i]]f[j−w[i]] 是已经更新后的结果，也就是 f[i][j−w[i]]f[i][j−w[i]] 。而倒序枚举则是未更新的结果，也就是 f[i−1][j−w[i]]f[i−1][j−w[i]] 。

for(int i=1; i<=n; i++){for(int j=w[i]; j<=W; j++){f[i][j] = max(f[i][j],f[i][j - w[i]] + c[i]);}
}

空间复杂度 O(W)O(W) 。

多重背包问题

有了每种物品只有1个的，也有每种物品无数多个的，自然有介于中间的形态：

P2552 多重背包I：有一个重量为 WW 的背包，你有 nn 种物品，第 ii 种物品都有 aiai​ 个，其中第 ii 种物品的重量为 wiwi​ ，价值为 cici​ 。你希望选出其中的一些装入背包，使得他们的重量之和不超过 WW 的前提下价值最大。

n≤1000n≤1000 ， W≤2000W≤2000 ， 1≤ai,wi,ci≤20001≤ai​,wi​,ci​≤2000 。

对于多重背包，我们是不是可以把 aiai​ 个第 ii 种物品，看成 aiai​ 个单独的物品，这样不就变成了 01 背包吗？

代码如下：

for(int i=1; i<=n; i++) {for(int k=1; k<=a[i]; k++) { // a[i] 件物品，每件枚举一次，当作一个物品for(int j=W; j>=w[i]; j--) {f[j] = max(f[j], f[j - w[i]] + c[i]);}}
}

时间复杂度 O(W∑i=1nai)O(W∑i=1n​ai​) 。

对于多重背包，上述做法需要付出很大的时间代价（至少是比 01 背包和完全背包要多的），于是我们提出了二进制优化和单调队列优化。

多重背包的二进制优化

仍然沿着 拆分物品 的方向去思考，如果我们能让拆分出的物品个数不是 a[i]a[i] 个，而是远小于 a[i]a[i] ，是不是时间复杂度就会降低很多了呢？考虑二进制的思想，我们考虑把第 ii 种物品换成若干件物品，使得原问题中第 ii 种物品可取的每种策略——取 0..a[i]0..a[i] 件——均能等价于取若干件代换以后的物品。另外，取超过 a[i]a[i] 件的策略必不能出现。

方法是：将第 ii 种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,...,2k−1,a[i]−2k+11,2,4,...,2k−1,a[i]−2k+1 ，且 kk 是满足 a[i]−2k+1>0a[i]−2k+1>0 的最大整数。例如，如果 a[i]a[i] 为 1313 ，就将这种物品分成系数分别为 1,2,4,61,2,4,6 的四件物品。

分成的这几件物品的系数和为 a[i]a[i] ，表明不可能取多于 a[i]a[i] 件的第 ii 种物品。另外这种方法也能保证对于 0..a[i]0..a[i] 间的每一个整数，均可以用若干个系数的和表示，这个证明可以分 0..2k−10..2k−1 和 2k..a[i]2k..a[i] 两段来分别讨论得出，并且总段数不超过 log⁡a[i]loga[i] ，这个并不难，希望你自己思考尝试一下。

这样就将第 ii 种物品分成了 O(log⁡ai)O(logai​) 种物品，将原问题转化为了复杂度为 O(V⋅∑i=1nlog⁡ai)O(V⋅∑i=1n​logai​) 的 01 背包问题，是很大的改进。

PS: 多重背包问题同样有 O(nW)O(nW) 的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊 O(1)O(1) 的时间求解，这个方法我们将在后续课程中讲解。

练习

• P1417 01背包问题I
• P2081 完全背包问题II
• P2552 多重背包I
• P1423 拔河比赛
• P1197 砝码称重
• P1509 楼梯
• P1513 积木搭建
• 01背包问题III
• P2533 完全背包问题III
• P2594 混合背包问题
• P1601 纪念品
• 搭配购买
• P2473 黄金矿工
• P4108 乘积凑零

LIS 的单调性优化

接下来，回到我们上一节课的 LIS 问题——

P2376 拦截导弹：给出一个长度为 nn 的序列 aa ，请你求出 aa 的最长不下降子序列。并请你求出将 aa 分组，使得每组都是最长不下降子序列，最少要分几组。

n≤105n≤105

一般来说，我们求 LIS 是用 dp 的方法来求的，它是基于这样的一个 dp 式子：设 f[i]f[i] 为以第 ii 个元素结尾的最长不下降子序列的长度。我们只需要在 ii 之前找到一个 jj ，满足 aj≤aiaj​≤ai​ ，那么就可以得到一种转移的方式 f[j]+1→f[i]f[j]+1→f[i] 。具体的就是 f[i]=max⁡j=1,aj≤aii−1(f[j]+1)f[i]=maxj=1,aj​≤ai​i−1​(f[j]+1) 。

这样直接转移是 O(n2)O(n2) 的，我们发现是转移寻找 max⁡f[j]maxf[j] 的过程，花费了我们太多的时间。我们考虑优化转移的过程。

对于第 1 位到第 i−1i−1 位的 f[j]f[j] ，如果存在两个位置 f[j]f[j] 相同，显然我只维护 a[j]a[j] 较小的那一个，因为如果我能从 a[j]a[j] 较大的那一个转移到 f[i]f[i] ，我定然也能从 ajaj​ 较小的那个转移，反之则不然。既然两者 f[j]f[j] 相同，我何尝不只记录 ajaj​ 较小的那一个呢？

于是我们新建一个数组 bb ， bibi​ 表示 f[j]=if[j]=i 的位置中， ajaj​ 的最小值是多少。可以推断， bb 数组内的数字是递增的。因此，当我找 f[i]f[i] 应该从哪个位置转移过来时，只需要根据 aiai​ 的大小，在 bb 数组中用二分法找到正好小于等于它的那个位置，让 f[i]f[i] 从这个位置转移过来。

时间复杂度 O(nlog⁡n)O(nlogn) 。

代码如下：

int n, a[N], f[N], b[N], cnt;b[0] = 0;
for (int i=1; i <= n; i++) {cin >> a[i];int t = upper_bound(b, b+cnt+1, a[i]) - b; // 找到 >= a[i]的第一个位置if(t > cnt) cnt++;b[t] = a[i];
}
cout << cnt;

再考虑第二问，第二问要求原序列最少能划分成多少个最长不下降子序列。根据 Dilworth 定理，这个就等于在原序列的逆序列中，最长不下降子序列的长度。因此我们再把原序列反过来，用相同的方法求 LIS。

Dilworth 定理：正串划分成的最少的最长不下降（上升）子序列数 = 反串最长不下降（上升）子序列长度。

排列 LCS 的优化

现在我们来考虑一类特殊的 LCS 问题：

P7544 最长公共子序列 II：给出两个 1∼n1∼n 的排列 a,ba,b ，换而言之，一个序列中没有两个相同的数。求两个排列的 LCS。

a,b≤100000a,b≤100000

我们不妨将 aa 的第一个元素 a1a1​ 映射到 11 ， aa 的第二个元素 a2a2​ 映射到 22 ……同时我们也修改 bb 中对应元素，将他修改为映射过后的结果。这样显然不改变 LCS 的大小。

我们将上面和下面的元素写在纸上，将两者数字相同的位置连一条线。那么 LCS，就是求出尽量多的连线，使得这些连线互不相交。

由于连线互不相交，我们观察 aa 中选出的元素在 bb 中有没有什么特征。可以发现，它在 bb 中构成一个上升子序列，我希望尽量多的连线被选出，于是问题就可以转化为选出尽量长的上升子序列，也就是最长上升子序列，套用上面 O(nlog⁡n)O(nlogn) 求 LIS 的方法，即可将这种特殊的 LCS 优化到 O(nlog⁡n)O(nlogn) 。

练习

• P1703 最长上升子序列（升级）
• P2874 搭积木 —— 能不能看出来可以化成 LIS 问题
• P2663 打鼹鼠
• P5894 最佳足球队
• P5934 上升点列

---

升级版（无题号）

题面

相比于上道题，我现在告诉你 aa 是由两个排列打乱构成的（ 1∼n1∼n 中的每个数字都出现两次）， bb 是由三个排列打乱构成的（ 1∼n1∼n 的每个数字出现三次）。请你求出这种情况下的最长公共子序列。

n≤100000n≤100000

分析

这题是上题的升级版，每个元素在序列中出现的次数不止一次，但是相同的数字在一个序列中出现的次数并不多。因此我们考虑改进上一题所述的算法。

上一题的做法我们其实可以换一种表述：假设 aiai​ 和 bjbj​ 数字相同，那么我可以构造一个二元组 (i,j)(i,j) 。我的问题可以看成，在 nn 对二元组中，选出尽量多对，使得选出的任意两对（下标为 x,yx,y ），都满足当 ix<iyix​<iy​ 时， jx<jyjx​<jy​ 。于是我可以将这一维排序，而将这一维用 LIS 优化求解。（类似于逆序对的一维排序，二维分治）

这道题也是相似的，我可以将 aiai​ 和 bjbj​ 数字相同的位置，抽象成一个二元组 (i,j)(i,j) ，这样只会有 6n6n 个二元组。我们只需要选出尽量多的二元组，使得任意两对满足 ix<iyix​<iy​ 的点对，也满足 jx<jyjx​<jy​ 。为了满足这个条件，也是为了满足一个点不会被重复选两次，我们可以按 ii 为第一关键字从小到大排序， jj 为第二关键字从大到小排序，然后求最长上升子序列即可。

时间复杂度 O(nlog⁡n)O(nlogn) ，带一个常数。