Ctrl+K

动态规划

动态规划#

date:

2021-05-18

排列组合问题#

参考：

顺序的有关与无关。

排列

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

  • 全排列 = n!

  • 排列数 组合数 * 全排列

组合

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

  • 「全组合」= 1

  • 组合数 排列数 / 全排列

概念 [1]#

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

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

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

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

背包九讲 [2]#

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 的常数优化#

:’( 不想看算了吧。

参考#

评论

如果你有任何意见，请在此评论。 如果你留下了电子邮箱，我可能会通过 回复你。

目录