算法基础课——动态规划（一）笔记

作者：

jaylenwanghitsz , 2022-02-28 22:30:02 , 所有人可见 , 阅读 380

2

1

背包问题

动态规划重点：状态表示 & 状态转移
定义：有编号为 $1$ ~ $N$ 的 $N$ 个物品和一个体积为 $V$ 的背包，对于每个物品 $i$ ，体积 $v_{i}$ ,价值（权重） $w_{i}$ 。要求往背包内装物品，在装入背包物品总体积不超过背包体积的前提下，求背包内物品价值总和的最大值
分析思路
- 状态表示
  - 可以把动态规划思想理解为每一个局面的最佳规划取决于上一个选择更少、更加简单的局面，不断递归求出题目给出局面的最佳规划
  - $f(c_{1},c_{2},…,c_{n})$ 表示一个 $n$ 维的局面
    - 每一维是用来确定局面的一个条件（比如背包问题的局面由容量和选择范围确定）
    - 每个局面是所有满足条件的规划的集合
    - 每个集合有特定的属性，比如最大值，最小值，最多数量等，一般由题目要求的量决定
    - $f(c_{1},c_{2},…,c_{n}) = character$ 存储属性
- 状态计算（状态转移方程）
  - 对应局面表示的集合的划分
  - 每个集合可以划分成更小的集合，这些小集合对应的每一维的条件也更小
  - 一般可以以一维条件的改变来划分集合
  - 集合划分后，由更小的集合的属性来递推大集合的属性

特点：物品件数无限制
二维状态 + 三重循环（TLE）
- 状态表示
  - 集合：f(i,j)
  - 属性：max
- 状态计算
  - 按 $i$ 的个数为 $0,1,2,3,…,k(k\times v_{i}<j)$ 来划分集合
  - f(i,j) = max(f(i - 1,j - 0 * v[i]) + 0 * w[i],f(i - 1,j - 1 * v[i]) + 1 * w[i],f(i - 1,j - 2 * v[i]) + 2 * w[i],...,f(i - 1,j - k * v[i]) + k * w[i])
二维状态 + 二重循环
- f(i,j)= max(f(i-1,j-0*v[i])+0*w[i],f(i-1,j-1*v[i])+1*w[i],f(i-1,j-2*v[i])+2*w[i],...,f(i-1,j-k*v[i])+k*w[i])
- f(i,j-v[i])= max(f(i-1,j-1*v[i]),f(i-1,j-2*v[i])+1*w[i],...,f(i-1,j-k*v[i])+(k-1)*w[i])
- 可以发现，f(i,j) = max(f(i - 1,j),f(i,j - v[i]) + w[i]) 由此只需要两重循环
- 与 $01$ 背包方程的区别：$01$ 背包中条件为 j - v[i] 的状态是 $i-1$ 条件下的，而完全背包是 $i$ 条件下的
一维状态 + 二重循环
- 完全按照 $01$ 背包问题的优化方式来优化
- 唯一不同在于，遍历 $j$ 时需要从小到大，理由是$01$ 背包中条件为 j - v[i] 的状态是 $i-1$ 条件下的，而完全背包是 $i$ 条件下的，因此 $j - v[i]$ 需要比 $j$ 更早更新
代码

对前一题的优化
- 不能按照完全背包的优化方式来优化，因为物品个数有限制，因此 f[i,j-v[i]] 最后会多出一项 f[i-1,j-(s+1)v[i]]+s*v[i] ,就不能直接替换优化了
- 优化方法：二进制优化
  - 把 $s_{i}$ 分解为 $1,2,4,8,…,2^{k},s_{i}-(2^{k+1}-1)$ ,这 $k+2$ 个数可以在每个数只用一次的前提下组合出 $1$ ~ $s_{i}$ 之间的所有数
  - 这样不仅 $s$ 的规模降到了 $\log s$ ，且整体的问题也等价于 $01$ 背包问题，就可以直接使用 $01$ 背包问题的优化解法
代码