动态规划

动态规划#

参考：

顺序的有关与无关。

排列

组合

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] <- -∞

备注

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

:'( 不想看算了吧。

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