Acwing-算法基础课-笔记（十二）

动态规划（Dynamic Programming，简称DP）章节

从两个角度进行讲解

1. 常用的DP模型
   • 背包问题
2. DP的不同类型
   • 线性DP
   • 区间DP
   • 状态压缩DP
   • 树形DP
   • 计数类DP
   • 数位统计DP

动态规划没有代码模板，它更偏向数学，其比较核心的部分在于状态的表示和状态的转移。

共3小节，第一小节预计讲解背包问题。

动态规划（一）

什么是背包问题？

背包问题的本质是，给定一堆物品和一个背包，每个物品有 体积 和 价值两种属性，在一些限制条件下，将一些物品装入背包，使得在不超过背包体积的情况下，能够得到的最大价值。根据不同的限制条件，分为不同类型的背包问题。

0-1 背包

给定

N 个物品，和一个容量为

V 的背包，每个物品有2个属性，分别是它的体积

vi​ （v for volume），和它的价值

wi​（w for weight） ，每件物品只能使用一次（0-1背包的特点，每件物品要么用1次（放入背包），要么用0次（不放入背包）），问往背包里放入哪些物品，能够使得物品的总体积不超过背包的容量，且总价值最大。

DP问题，通常从2方面来思考：状态表示和状态计算

• 状态表示

  从2方面考虑

  • 集合（某一个状态表示的是哪一种集合）
  • 属性（这个状态存的是集合的什么属性）
    • 集合的最大值
    • 集合的最小值
    • 集合中的元素个数

• 状态计算

  状态转移方程。即集合的划分。比如对

  $f(i,j)$

  f(i,j) ，考虑如何将其划分成若干个更小的子集合，而这些更小的子集合，又能划分为更更小的子集合。

  集合的划分有2个原则：

  • 不重：即不重复，某个元素不能既属于子集合A，又属于子集合B
  • 不漏：即不漏掉任一元素，某个元素不能不属于任何一个子集合。

  通常需要满足不漏原则，而不重不一定需要满足。

比如对01背包，用状态

f(i,j) 来表示所有选法（选择哪些物品）的集合。并且

i，

j 的含义是：只从前

i 个物品中进行选择，

j 表示，选出来的总体积小于等于

j 。

f(i,j) 的值是最大的总价值。

即，用

f(i,j) 来表示，只从前

i 个物品中选，且选出来的物品的总体积小于等于

j 时，能够选出来的，最大的总价值。

01背包的最终答案应该是

f(N,V) ，即从前

N 个物品中，选出总体积不超过

V ，能够得到的最大价值。

现在来考虑状态的计算，对于

f(i,j) 划分为2大类，一是不包含第

i 个物品的选法，二是包含

i 的选法。

那么，左侧选法的最大价值就是

f(i−1,j)，右侧选法的最大价值就是

f(i−1,j−vi​)+wi​ 。则

f(i,j)的最终取值，就是左右两侧较大的那一个，即

f(i,j)=max{f(i−1,j),f(i−1,j−vi​)+wi​}

练习题：Acwing - 2 01背包问题

朴素做法（用二维数组来表示状态，注意右侧集合可能不存在，当

j<vi​ 时，即当可用体积小于第

i 个物品的体积时）

#include <iostream>

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if(j >= v[i]) f[i][j] = std::max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
	}
	printf("%d", f[n][m]);
}
复制代码

优化

（原先用二维数组表示状态，可以换成一维数组，用滚动数组的方式。注：动态规划的优化，通常都是对代码或者状态转移方程，做等价变型）

#include <iostream>

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= n; i++) {
		for(int j =m; j >= v[i]; j--) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]);
		}
	}
	printf("%d", f[m]);
}
复制代码

用一维数组进行优化，一开始有点不好想，此时可以把中间的状态转移的过程打印出来，方便理解。由于计算

f(i,j)时，需要依赖

f(i−1,j)，所以在

i 的层面，必须从

1 开始枚举到

n ，先计算

i 较小时的

f，才能迭代计算后面的。所以

i 的枚举不能逆序。

然而我们发现，对于外层循环

i，每一次循环，都会使用到

i−1 这一层的

f，则可以采用一维数组进行优化，而由于进行更新时，需要用较小的

j 的

f 去更新较大

j 的

f，如果

j 也从小到大进行迭代，则在更新

f(j) 时，使用的

f(j−v[i]) ，由于

j−v[i]<j，则

f(j−v[i]) 一定先于

f(j) 更新。当更新

f(j) 时使用的

f(j−v[i])，实际上已经是更新后的值，即

f(i)(j−v[i]) 了，所以我们要逆序枚举

j ，从大到小枚举

j，则能保证更新

f(j) 时，使用的

f(j−v[i]) 还未被更新，即其还是上一轮的

f(j−v[i])，即其为

f(i−1,j−v[i])

例子如下：假设

N=4，

V=5，对于

i=0，其

f 全为0。物品的体积和价值分别为：

v1​=1，

v2​=2，

v3​=3，

v4​=4

w1​=2，

w2​=4，

w3​=4，

w4​=5

动图图解：

由于每一轮计算只依赖于上一行的

f，所以可以用滚动数组的思想，使用一维数组来存储

f，由于更新的时候，

f(j) 需要依赖于上一轮的

f(j−v[i])，所以枚举

j 时，从大到小枚举，才能保证

f(j) 的更新，要早于

f(j−v[i])，从而保证是用上一轮的

f(j−v[i]) 来更新的

f(j) 。

完全背包

定义与 0-1 背包类似，只是每件物品可以用无限次

回忆一下，动态规划的2个思考角度：状态表示，状态计算。

状态表示：和 01 背包完全一样。

状态计算：和01背包不同。01背包是按照第

i 个物品选或者不选，分为了2类。完全背包，可以按照第

i 个物品选多少个，来分成若干组。比如，第0个子集表示，第

i 个物品选0个，第1个子集表示，第

i 个物品选 1 个，第2个子集表示选2个，....，第n个子集表示选n个（假设最多只能选n个，否则背包容量不够）。

则其状态转移方程为：

f(i,j)=max{f(i−1,j−k×v[i])+k×w[i]}，其中

k∈[0,n]

练习题：Acwing - 3. 完全背包问题

先按照上面的状态计算方式，写一个朴素版的动规

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX];

int main() {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
			for(int k = 0; j >= k * v[i]; k++)
			    f[i][j] = std::max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	}
	printf("%d", f[N][V]);
}
复制代码

提交后发现报TLE，超时了，于是我们想一下如何优化。

根据上图的推导过程，我们实际上可以用2个状态来推导出

f(i,j)，即

f(i,j)=max{f(i−1,j),f(i,j−v)+w}，此时

f(i,j)的推导就和

k 无关了。于是根据这个状态转移方程，我们写成代码如下

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX];

int main() {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
		    f[i][j] = f[i - 1][j];
			if(j >= v[i]) f[i][j] = std::max(f[i][j], f[i][j - v[i]] + w[i]);
		}
	}
	printf("%d", f[N][V]);
}
复制代码

这次提交就AC啦。

随后我们观察到，仍然可以将二维数组通过滚动数组的思想，优化成一维数组，如下：

（这跟01背包的优化略有不同，因为

f(i,j)依赖于f(i,j−v[i])，依赖于本行，而不是上一行，所以

j 的枚举要从小到大，保证在更新

f(i,j)时，

f(i,j−v[i]) 已经更新过了）

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX];

int v[MAX], w[MAX];

int main() {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = v[i]; j <= V; j++) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]);
		}
	}
	printf("%d", f[V]);
}
复制代码

可以发现，完全背包和01背包的状态转移方程非常相似

01背包：

f(i,j)=max{f(i−1,j),f(i−1,j−v[i])+w[i]}

完全背包：

f(i,j)=max{f(i−1,j),f(i,j−v[i])+w[i]}

在进行一维数组优化时，由于01背包的

f(i,j) 依赖于上一行（

i−1 行）的状态（即

f(i−1,j−v[i])）,所以要保证更新

f(j) 时，

f(j−v[i])仍然是上一行的值，即

f(j) 要先更新，

f(j−v[i])要后更新，所以

j 的枚举要从大到小。

而完全背包恰好相反，

f(i,j)依赖于本行的状态（即

f(i,j−v[i])），所以要保证在更新

f(j)时，

f(j−v[i]) 已经更新过了，所以

j 的枚举要从小到大。

多重背包

每件物品的个数是不同的，比如，每件物品的个数是

si​ 个。

多重背包的状态转移方程，和完全背包一致，如下

f(i,j)=max{f(i−1,j−v[i]×k)+k×v[i]}，

k∈[0,s[i]]

多重背包只是对每个物品，多了数量限制，而完全背包没有数量限制。

练习题：Acwing - 4. 多重背包问题I

朴素版题解：

#include <iostream>

const int MAX = 1010;

int N, V;

int f[MAX][MAX];

int v[MAX], w[MAX], s[MAX];

int main() {
	scanf("%d%d", &N, &V);
	for(int i = 1; i <= N; i++) scanf("%d%d%d", &v[i], &w[i], &s[i]);

	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= V; j++) {
			for(int k = 0; j >= k * v[i] && k <= s[i]; k++)
			    f[i][j] = std::max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	}
	printf("%d", f[N][V]);
}
复制代码

朴素版的代码，和完全背包的几乎一模一样，只是内层循环多了个

k≤s[i] 的条件，尝试提交后竟然AC了。这是因为该题N的范围比较小，最大只到100，而朴素做法的时间复杂度是

O(n3)，所以时间复杂度最多为

108，然而下面的这道题目，由于数据范围变大，朴素做法便行不通了：Acwing - 5. 多重背包问题II

下面考虑一下如何进行优化

首先，还是按照完全背包的优化思路，推导一下状态转移方程：（下面用 v来代表 v[i]，w代表w[i]，s代表s[i]）

f[i,j]   = max(f[i-1,j], f[i-1,j-v] + w, f[i-1,j-2v] + 2w ,..., f[i-1,j-sv] + sw)
f[i,j-v] = max(          f[i-1,j-v],     f[i-1,j-2v] + w  ,..., f[i-1,j-sv] + (s-1)w + f[i-1,j-(s+1)v] + sw)
复制代码

可以看到，两个状态转移方程，只有中间一部分是相同的，无法进行替换。

二进制优化

考虑用一种二进制的方式，比如对于某个 i，其s[i]=1023，则对于该物品，一共需要枚举0,1,2,3,....,1023，共1024种情况。我们可以这样：只保留2的幂的数，然后其他数用2的幂来凑。

比如对0到1023，我们只保留1,2,4,8,16,...,512，共10个数字，则0到1023的任意数字，都能由这10个数字组合相加得到。（其实这个思想的本质就是把一个十进制的数，化成二进制表示）。这样以来，我们无需枚举0到1023，只需要枚举1,2,4,8,...,512这10个数即可 。

上面是恰好s[i]=1023，共枚举

210种情况，假设s[i]不是2的幂呢？比如s[i]=200，此时我们需要1,2,4,8,16,32,64，此时不能要128，因为加上128后，能凑出的数的范围就超过200了，而1,2,4,8,16,32,64能凑出的最大的数是127，和200还差73，所以我们补上一个数字73，即我们使用1,2,4,8,16,32,64,73就能凑出0到200内的任意一个数字了。

如何证明使用这几个数就能凑出0到200里的任意一个数字呢？

首先1,2,4,8,16,32,64能够凑出0到127，这是毋庸置疑的。而0到127种的任意一种组合，再额外加一个73，就能凑出73到200，所以上面的8个数就能凑出0到200中的任意一个数。

所以，对于物品i，共有s[i]个，其实我们可以把s[i]个物品，拆分成

logs[i]​ 个新的物品。然后对这些新的物品，做一次01背包问题即可。

#include <iostream>

// 因为物品共有N=1000个，而每个物品的s[i]最大到2000，所以每个物品能拆成log(2000)≈11, 实际计算出来是小于11的,
// 所以拆分后的物品总数不超过 1000 * 11 = 11000, 所以我们的N开到11000即可
const int N = 11000;

int n, m;

int v[N], w[N], f[N];

int main() {
	scanf("%d%d", &n, &m);
	int cnt = 0;

	for(int i = 1; i <= n; i++) {
        // 处理输入, 将 s[i] 个物品拆分成 log(s[i]) 个
		int a, b, s;
		scanf("%d%d%d", &a, &b, &s);
		int k = 1;
		while(k <= s) {
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if(s > 0) {
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}

	n = cnt; // 总共拆分成了多少个新的物品

    // 对新的物品, 做一次01背包问题, 这里直接写了一维数组优化后的01背包
	for(int i = 1; i <= n; i++) {
		for(int j = m; j >= v[i]; j--) {
			f[j] = std::max(f[j], f[j - v[i]] + w[i]);
		}
	}

	printf("%d", f[m]);
}
复制代码

分组背包

有

N 组物品，每一组中有若干个物品，每一组中至多选择一个。

分组背包问题的思考方式和前面的类似。不同的地方仅仅在于状态转移。

01背包的状态转移，是枚举第i个物品选或者不选；

完全背包和多重背包，是枚举第i个物品，选0,1,2,3,4,.... 个

而分组背包，枚举的是第i个分组，选哪一个，或者不选

分组背包的状态转移方程为：

f(i,j)=max{f(i−1,j),f(i−1,j−v[i,k])+w[i,k} ，

k∈[1,s[i]]

其中

v[i,k] 表示第

i 组中的第

k 个物品的体积，

w[i,k] 同理

练习题：Acwing - 9. 分组背包问题

#include <iostream>

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		for(int j = 0; j < s[i]; j++) {
			scanf("%d%d", &v[i][j], &w[i][j]);
		}
	}

	for(int i = 1; i <= n; i++) {
		for(int j = m; j >= 0; j--) {
			for(int k = 0; k < s[i]; k++) {
				if(v[i][k] <= j) {
					f[j] = std::max(f[j], f[j - v[i][k]] + w[i][k]);
				}
			}
		}
	}
	printf("%d", f[m]);
}
复制代码