一. 背景
1.1 理论依据
算法导论动态规划章节的知识点和个人归纳总结与推广
1.2 例题描述(可跳过)
01背包问题
输入: $N$ 个物品, 背包容量为 $V$ , 物品 $i$ 有体积 $v_i$ , 价值 $w_i$ , 每个物品可选 1 个或 0 个
输出: 最大价值
1.3 动态规划概念理解
面向的问题: 通常都是最优化问题
最优化问题: 求一个问题的最值, 通常会有一些约束条件
如:
$\max x^2$
$\text{ s.t. } x\in[-1,1]$
对比部分可最后看
与贪心算法对比
- 贪心算法也面向最优化问题
- 贪心算法与动态规划都有最优子结构性质
- 动态规划多了一个重叠子问题性质
与分治法对比
-
分治法与动态规划都用到了递归的思想
这里的递归我更愿意用数学上的递推来描述, 即用递推式表述分治法与动态规划中都有的“用子问题的解组合为原问题的解/原问题的解分解为子问题的解”思想
递推式即高中数列通项中 $a_n$ 与 $a_{n-1}$, $a_{n-2}$… 的递推公式, 如 $a_n = a_{n-1} + 1$, $a_1 = 0$
本文也将不会使用状态转移方程的说法
-
分治法的划分会产生很多新的子问题, 动态规划的选择会产生很多重复的子问题, 即重叠子问题性质
二. 动态规划总览
2.1 数学模型
$\max/\min f_总$
$\text{ s.t. } x\in D$
其实 $f_总$ 本身已经含有问题的最优解(最大值, 最小值)这一概念了
2.2 递归式
$f_原 = g(f_子), f_基 = init$
- $f_原$ 表示原问题的最优解, 默认为一个值
-
$f_子$ 表示子问题的最优解, 默认为一到多个值, 即由多个子问题的最优解组成一个原问题的最优解
-
$g$ 是子问题与原问题的函数关系, 一般为 $\max/\min\{分类讨论的所有情况/选择产生的所有情况\}$
-
$f_基$ 表示基础问题, 相当于递归的 base case 或数学归纳法的 base case, 由初始化给定值
- 此递归式就是所谓的状态转移方程
2.3 设计动态规划算法的步骤
-
刻画最优解的结构特征
确定最优子结构
-
递归定义最优解
写递推式
-
自底向上计算最优解
或自顶向下备忘录计算最优解
-
构造最优解
重建最优解的解法, 不单单是输出一个最大值/最小值, 而是输出通过哪些选择得到最值的, 一般的问题不要求输出构造最优解的过程
三. 解题步骤
01背包问题
输入: $n$ 个物品, 背包容量为 $v$ , 物品 $i$ 有体积 $v_i$ , 价值 $w_i$ , 每个物品可选 1 个或 0 个
输出: 最大价值
步骤一 刻画最优解的结构特征(最最重要,唯一难点)
1.1 先用递归方法暴力穷举所有情况
先用递归/贪心/分治的思想处理问题, 看看有哪些情况
这个过程不考虑约束条件, 或者说: 这个过程只是粗略看一下递归的所有情况, 不考虑细枝末节
其实本质都是递归的思想, 只不过有时候是像贪心那样的线性递归, 有时候是像分治那样的二分递归
解题过程如下:
1. 所有情况个数
n 个物品, 每个物品可选 1 个或 0 个, 即每个物品有两种选择
显然, 总共有 $2^n$ 种情况
2. 尝试用递归的思想来描述问题间的关系
定义:
$f_i$ 表示仅考虑前 $i$ 个物品时的最大价值
$f_{i-1}$ 表示仅考虑前 $i-1$ 个物品时的最大价值
$a_i$ 表示仅考虑前 $i$ 个物品时的情况个数
$a_{i-1}$ 表示仅考虑前 $i-1$ 个物品时的情况个数
假定背包容量无限大, 反正只是粗略看一下问题间的关系, 不考虑细枝末节
递归:
显然, 对每个物品来说有两种情况: 选 1 个或选 0 个
当问题规模为前 $i$ 个物品的最大价值时, 只考虑第 $i$ 个物品的话有两种选择: 选 1 个或选 0 个
做出选择之后, 就要考虑剩下的 $i-1$ 个物品的最大价值问题了
即, $f_i = \max\{选1个后的 f_{i-1}, 选 0 个后的 f_{i-1}\}, f_0 = 0$
同样的, $a_n = 2a_{n-1}, a_0 = 1$
$f_0 = 0 表示前 0 个物品最大价值为 0$
$a_0 = 1 表示前 0 个物品只有选 0 个这一种情况$
1.2 寻找最优子结构
最优子结构:
某问题的最优解包含其子问题的最优解
含义解释:
- 子问题的最优解映射(构造/组成/得到)为其原问题的最优解
- 子问题的最优解包含了子子问题的最优解, 直到遇到基础解
- 子问题之间是独立的, 互不影响(子问题无关性)
寻找最优子结构步骤
1.2.1 证明问题的最优解要通过做出一个选择来得到
对于前 $i$ 个物品的最大价值问题 $f_i$ ,
考虑到 $f_i$ 为前 $i-1$ 个物品的最大价值,
我们可以对第 $i$ 个物品选择装入 $1$ 个或 $0$ 个来得到两个不同的子问题 $f_{i-1}$
此时不考虑背包容量的影响, 因为背包容量是约束条件, 相当于是剪枝, 对于最优子结构无影响
对于任何一个规模的问题都可以做出这样的选择来得到其子问题,
即, 01背包问题的最优解可以通过选择装入 $1$ 个或 $0$ 个当前物品来得到, 两个选择会产生两个不同的子问题
1.2.2 假定已知做出哪种选择会得到问题的最优解
假定 01 背包问题选择装入 $k$ 件当前物品会得到最优解, $k\in\{0, 1\}$
1.2.3 得到最优选择后, 确定该选择会产生哪些子问题, 以及如何刻画合适的子问题空间
这一步的目的其实是一般化展示做出选择后问题与子问题的通用关系式
如果不太好确定通用的关系式, 可以把所有的选择和关系式都列出来
对于前 $i$ 个物品, 背包空间为 $j$ 的最大价值问题, 最优选择为选 $k$ 件第 $i$ 个物品, $k\in\{0, 1\}$
产生的子问题为前 $i-1$ 个物品, 背包容量为 $j - k\cdot v_i$ 的最大价值
若第一时间想不出通用的关系式, 可以列出所有的选择的关系式
做出选 $1$ 件的选择:
子问题为: 前 $i-1$ 个物品, 背包容量为 $j-v_i$
做出选 0 件的选择:
子问题为: 前 $i-1$ 个物品, 背包容量为 $j$
由于物品个数 $i$ 和背包容量 $j$ 都是在变化的, $i$ 变为 $i-1$, $j$ 变为 $j - k\cdot v_i$
所以子问题空间要有两个维度, 一个用来表示物品个数的变化, 一个用来表示背包容量的变化
即, 定义 $f(i, j)$ 表示问题为前 $i$ 个物品, 背包容量为 $j$ 的最大价值
则在最优选择为 选 $k$ 件 的条件下, $f(i,j) = f(i-1,j-k\cdot v_i) + k \cdot w_i$
在 1.2.4 证明之后, 才能说 $f(i-1,j-k\cdot v_i)$ 的含义是
子问题前 $i-1$ 个物品, 背包容量为 $j - k\cdot v_i$ 的最优解
此处 $f(i,j)$ 的含义是问题的最优解, $f(i-1,j-k\cdot v_i)$ 的含义是子问题的解
1.2.4 反证法证明原问题的最优选择产生的子问题的解是子问题的最优解
有些地方叫剪贴法, 本质上还是反证法
反证法套路: 假设子问题的解不是其最优解, 则将子问题的最优解带入原问题的最优选择后会产生一个更优的解,
这与”原问题做出最优选择后得到原问题的最优解“的假设矛盾, 故子问题的解是最优解
假设 $f(i-1,j-k\cdot v_i)$ 不是子问题 $(i-1,j-k\cdot v_i)$ 的最优解
则将其最优解带入 $f(i,j) = f(i-1,j-k\cdot v_i) + k \cdot w_i$ 后, $f(i, j)$ 会变得更优, 产生矛盾
所以 $f(i-1,j-k\cdot v_i)$ 是子问题 $(i-1,j-k\cdot v_i)$ 的最优解
即问题$(i, j)$ 做出最优选择后的子问题 $(i-1,j-k\cdot v_i)$ 的解是其最优解
公式 $f(i,j) = f(i-1,j-k\cdot v_i) + k \cdot w_i$ 里面的 f 都是对应问题的最优解
步骤二 递归定义最优值
在确定最优子结构后, 就可以真正写出递推式了, 此时要把约束条件考虑进去
$f(i, j)$ 表示前 $i$ 个物品, 背包容量为 $j$ 时的最大价值
-
base case 基础情况
$i = 0$ 时, 没有物品, 容量再大, 价值也是 $0$
故 $f(0,j) = 0, j = 0,1…V$
-
step case 递归情况
$i > 0$ 时,
- 选第 $i$ 件的价值为 $f(i-1,j-v_i)+w_i$, 要求 $j-v_i>=0$
- 不选第 $i$ 件的价值为 $f(i-1,j)$
而 $f(i,j)$ 的含义是最大价值, 故
$f(i,j) = max\{f(i-1,j), f(i-1,j-v_i)+w_i\}$, 若 $j-v_i<0$, 则没有第二项
步骤三 自底向上计算最优解
普通的求解
确定递推式后, 就可以写代码计算最优解了, 一般的动态规划问题到这里也就结束了
在这一步骤, 如果仅仅只是普通地求出解,
那么依靠感觉, 或者依靠$f(i,j)$ 依赖于子问题 $f(i-1,j)$ 和 $f(i-1,j-v_i)$
就可以简单判断出可以用下面这种遍历顺序来求解最优解
i = 1 to N
j = 1 to V
关键代码为
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= V; j++)
{
if(j < v[i])
f[i][j] = f[i-1][j];
else
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
}
}
初学动态规划不建议去了解一些没什么用的奇淫技巧
如滚动数组(或叫做二维转一维)及其逆序更新, 还有用 $f$ 的空间去代替一些记录必要信息的空间, 或者边输入边计算
这些对与时间复杂度的量级优化没有任何影响, 即使对判断条件进行优化, 也只是 O(1) 级别的优化,
对程序的执行速度几乎没有影响, 反而会带来很大的理解负担
滚动数组这些空间复杂度的优化也是没有什么必要的, 因为计算机发展到现代, 程序的时间复杂度比空间复杂度更加重要
机试题给的空间也都是足够的, 重点在于时间复杂度
遍历顺序的深刻理解
如果想对遍历顺序有一个深刻的理解和理解空间复杂度的优化(即常说的滚动数组或二维转一维)
就需要做一些额外的分析, 简单来讲就是根据原问题与子问题的依赖关系来判断
-
先确定一个原问题要用到(或者说依赖)哪些子问题
对于 01 背包问题, 显然 $f(i,j)$ 依赖于子问题 $f(i-1,j)$ 和 $f(i-1, j-v_i)$
-
画图
根据依赖关系画图, 其中依赖的子问题要重点标注出来
-
确定可以使用哪些遍历顺序及哪些遍历顺序可以优化空间复杂度
先行后列遍历
- 行之间: 第 $i$ 行依赖于第 $i-1$ 行
显然行的遍历顺序为 $i = 1 \rightarrow N$ - 某一行的元素间: $f(i,j)$ 并不依赖该行的其他任何元素
则列的遍历顺序为 $j = 1 \rightarrow V$ 或 $j = V \rightarrow 1$ - 则先行后列的遍历顺序为
i = 1 to N
j = 1 to V
或
i = 1 to N
j = V to 1
先列后行遍历
-
列之间: 第 $j$ 列依赖于第 $j$ 列和第 $j-v_i$ 列
则列的遍历顺序为 $j = 1 \rightarrow V$
-
某一列的元素间: $f(i,j)$ 依赖于该列的 $f(i-1,j)$ 元素
则行的遍历顺序为: $i = 1 \rightarrow N$
-
则先列后行的遍历顺序为
j = 1 to V
i = 1 to N
可供选择的所有遍历顺序有
先行后列
i = 1 to N
j = 1 to V
i = 1 to N
j = V to 1
先列后行
j = 1 to V
i = 1 to N
空间复杂度优化
TODO
步骤四 构造最优解
构造最优解不是输出最优解的值, 而是输出得到最优解的过程
即通过哪些选择(最优选择)一步一步得到最优解
方法就是用额外的空间记录下每次递推的最优选择
具体过程
对于 01 背包问题, 用 $s(i,j)$ 表示对于问题前 $i$ 个物品, 容量为 $j$ 时第 $i$ 个物品选几个
在每次 $f(i,j) = max\{f(i-1,j), f(i-1,j-v_i)+w_i\}$ 得到 $f(i,j)$ 的值时
-
若 $f(i,j)$ 由 $f(i-1,j)$ 得到, 说明第 $i$ 个物品最优选择为选 $0$ 个, 则 $s(i,j) = 0$
-
若 $f(i,j)$ 由 $f(i-1,j-v_i)$ 得到, 说明第 $i$ 个物品最优选择为选 $1$ 个, 则 $s(i,j) = 1$
记下所有问题的最优选择后, 依据问题的最优子结构特点逐步输出最优解的构造过程
记录最优选择
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= V; j++)
{
if(j < v[i])
{
f[i][j] = f[i-1][j];
s[i][j] = 0;
}
else
{
if(f[i-1][j] > f[i-1][j-v[i]]+w[i])
{
f[i][j] = f[i-1][j];
s[i][j] = 0;
}
else
{
f[i][j] = f[i-1][j-v[i]]+w[i];
s[i][j] = 1;
}
}
}
}
输出构造最优解的选择
// 由于是从 f(N, V) 逆推, 所以最优选择需要用一个数组倒序存储, 然后正序输出
for(int i = N, j = V; i >= 1; i--)
{
if(s[i][j] == 0)
{
a[i] = 0; // 没选择第 i 件物品的话, 背包容量 j 就不变
}
else
{
a[i] = 1;
j-= v[i]; // 选择第 i 件物品的话, 背包容量就减去第 i 件物品的体积
}
}
// 正序输出最优选择
for(int i = 1; i <= N; i++) cout << a[i] << " ";
cout << endl;
四. 具体代码与其他动态规划内容
01 背包问题的具体代码
朴素版本
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1010;
int N, V;
int v[M], w[M];
int f[M][M];
int main()
{
cin >> N >> V;
for(int i = 1; i <= N; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= V; j++)
{
if(j < v[i])
f[i][j] = f[i-1][j];
else
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
}
}
cout << f[N][V] << endl;
return 0;
}
空间复杂度优化后的版本
边输入边计算
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1010;
int N, V;
int f[M];
int main()
{
cin >> N >> V;
for(int i = 1; i <= N; i++)
{
int v,w;
cin >> v >> w;
for(int j = V; j >= v; j--)
f[j] = max(f[j], f[j-v]+w);
}
cout << f[V] << endl;
return 0;
}
其他动态规划内容
- 多重背包的二进制优化原因: 二进制是等价变形, 不是优化的原因, 优化另有其因
- 初始化的不同导致结果含义的不同
- 遍历顺序继续深入讲解
- …
牛啊
膜拜泉神
Orz
牛
牛啊
牛
牛
nwnw
大佬,牛!
牛蛙