动态规划

date

2021-05-18

排列组合问题 1

顺序的有关与无关

排列
  • 公式 m!/(m-n)!

  • 全排列 = n!

  • 排列数 组合数 * 全排列

组合
  • 公式 m!/n!(m-n)!

  • 「全组合」= 1

  • 组合数 排列数 / 全排列

概念 2

  1. 抽象问题 - 清晰的可枚举的问题

  2. 寻找可以利用的重复计算

  3. 重复计算定义为子问题

  4. 定义重复子问题之间的关系

和贪心的区别?

贪心的子问题是独立的,可不带 context 求解的

背包九讲 3

01 背包问题

问题抽象

F[i, v] 为前 i 件物品放入容量为 v 的背包时的最大价值,即此时的 [0, i] 的物品都做出了 未知但正确 的选择,面对「放不放 i」这个问题,选择的方式是

F[i, v] = max(F[i-1, v-Ci] + Wi, F[i-1, v])

第一眼会有 「明显是放 i 价值更大啊,放了总是多出 Wi 来」的错觉 ,注意: 问题不是线性求解的F 是个矩阵而不是数组, `F[i, v]` 和 `F[i-1, v]` 都是把背包放满了的最优解,并且选择方式可能完全不一致

注解

比较感慨的是大学时期理解得很费劲的东西,现在看上去并不可怕

从思路到伪代码:

F[0, 0..V ] <- 0
for i <- 1 to N
   for v <- Ci to V
      // 从「刚好放满」膨胀到题设的容量 V
      F[i, v] <- max(F[i-1, v], F[i-1, v-Ci] + Wi)

空间复杂度

在 1 to N 的循环里,F[i, v] <- max(F[i-1, v], F[i-1, v-Ci] + Wi) 说明 F[i, v] 只依赖上一次循环(i-1)的结果,所以只需要存 F[i-1, Ci-1..V] 而不是矩阵 F[0..N, 0..V]:

// WARNING:: 错误的伪代码
F[0..V] <- 0
for i <- 1 to N
   for v <- Ci to V
      F[v] <- max(F[v], F[v-Ci] + Wi)

但这么写会发现原来是 F[i, v] 的值会在计算中覆盖 F[i-1, v] 的值(合并成一个数组了),V..0 倒着算就不会有问题了:

F[0..V] <- 0
for i <- 1 to N
   for v <- V to Ci
      F[v] <- max(F[v], F[v-Ci] + Wi)

恰好放满背包

原始问题仅要求了「价值最大」, 当挑选第一个物品时 F[1, v] = max(F[0, v-Ci] + Wi, F[0, v]) 是可以选择 F[0, v]v!=0 的,此时背包出现了空隙。

若要求恰好把背包放满,让其无法选 F[0,v] 即可:

F[0] <- 0
F[1..V] <- -∞

注解

当然这样的话可能出现无解的情况

Ci..V 的常数优化

:’( 不想看算了吧。

参考

1

https://www.zhihu.com/question/450108393/answer/1788658078

2

https://www.zhihu.com/question/39948290/answer/612439961

3

https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf